Tokenizer Fairness & Data Mixing

Chapter 1: Byte Pair Encoding, From Zero

Before we can talk about making a tokenizer fair, we need the exact mechanics of what a tokenizer is, stated precisely enough that “fair” can later become a formula rather than a slogan. We’ll build Byte Pair Encoding (BPE) the way the Parity-aware BPE paper itself defines it, symbol by symbol.

The raw material: bytes, not characters

Every piece of text, in any language, is at bottom a sequence of bytes — integers from a fixed alphabet 𝗁 = {0, …, 255}. Early tokenizers worked over characters, but bytes won out for a specific reason: 256 symbols can represent any character from any encoding, so a byte-level tokenizer never hits an out-of-vocabulary character. Feed it Cyrillic, emoji, or a stray control code and it degrades gracefully to individual bytes — it never needs an <UNK> token for something it hasn’t seen before.

Call a finite byte-string b. Tokenization is the process of grouping b’s bytes into larger chunks — subwords — so the model works with a shorter sequence of richer symbols instead of one symbol per byte. BPE is one specific, iterative recipe for deciding which groupings earn a place in the vocabulary.

A merge, defined precisely

A merge is an ordered pair m = (v, v′) of existing vocabulary symbols. Applying a merge to a token sequence means: find every adjacent occurrence of the bigram v, v′ and replace it with a single new symbol v ∘ v′ (their concatenation). Every replacement shortens the sequence by exactly one token — two symbols become one. Do this enough times and a 480,000-byte document becomes a few hundred tokens.

The tokenizer’s vocabulary after learning K merges is

— the 256 raw bytes, plus one new symbol for every merge you learned. Because the merge list m = [m1, …, mK] is fixed and ordered, encoding new text is completely deterministic: start from raw bytes, apply m1 everywhere it matches, then m2, and so on.

Watching it happen: the paper’s own toy example

Nothing beats tracing an example by hand. Here is the exact walkthrough the Parity-aware BPE paper uses to introduce merging, reproduced in full:

Two merges took a 5-byte string down to 2 tokens. That ratio — input length divided by output length — is not incidental. It is exactly the quantity BPE is trying to maximize, and it has a name.

Compression rate: the objective, made numeric

Define the compression rate of a byte-string b under tokenizer τ as

where |b|u is the length of b in some normalization unit u (bytes, characters, or — as we’ll need in Chapter 2 — aligned lines of parallel text) and |τ(b)| is the number of tokens the tokenizer produces. A higher CR means stronger compression: more raw content packed into each token the model has to process.

Worked example, hand-checked against the trace above. Using bytes as the unit, our toy string has |b|u = 5. Before any merges, every byte is its own token, so |τ(b)| = 5 and

After the two merges, |τ(b)| = 2 (the tokens ba, bab), so

Two merges improved compression by a factor of 2.5×. That is the whole game, at toy scale: BPE exists to push this number up as far as a fixed merge budget allows.

Averaged over a whole corpus 𝒟, the same idea becomes

This is a ratio of two sums, not an average of per-document ratios — long documents contribute more to both the numerator and the denominator. Keep that framing in mind; it matters the moment the corpus is a mixture of many languages.

The learning objective and the greedy algorithm that approximates it

Classical BPE learns its merge list by solving

— find the K-merge list that maximizes corpus-wide compression. Searching over every possible merge list is intractable, so BPE solves this greedily: start from the byte vocabulary and, at each of K steps, add whichever single merge helps the most right now, never revisiting the choice. Concretely:

python
# Algorithm 1 in the paper, as runnable pseudocode
V = set(range(256))          # V_0 = the byte alphabet
merges = []

for k in range(K):
    pair_counts = {}
    for doc in corpus:                     # count every adjacent (v, v') pair, corpus-wide
        for v, v2 in adjacent_pairs(doc):
            pair_counts[(v, v2)] = pair_counts.get((v, v2), 0) + 1

    best_pair = max(pair_counts, key=pair_counts.get)   # the single most frequent pair
    new_symbol = concat(best_pair)
    V.add(new_symbol)
    merges.append(best_pair)
    corpus = [apply_merge(doc, best_pair, new_symbol) for doc in corpus]  # replace everywhere

# tokenizing new text = apply `merges` in this exact order

Every step does exactly three things: count adjacent pairs across the whole corpus, take the single most frequent one, and replace it everywhere. Repeat K times and you have a full tokenizer. Notice what never changes across the whole run: the counting is always corpus-wide. Every document in 𝒟 votes on every merge, in proportion to how many matching pairs it contains.

The question this chapter leaves hanging

Equation 4 is a single number computed over one pooled corpus 𝒟. It has no idea that 𝒟 is secretly forty different languages glued together. If English contributes 40% of the bytes and Amharic contributes 0.03%, the pair-counting step in the algorithm above counts English pairs forty-times-plus more often — not because English “deserves” more merges, but because the objective has no concept of “language” at all. It only sees bytes. That gap between what the objective optimizes and what a multilingual product actually needs is the entire subject of Chapter 2.

Other ways to measure a tokenizer: fertility and vocabulary diversity

Compression rate is not the only lens the field uses on a tokenizer, and two more will matter once we reach the real, measured comparison table in Chapter 4. Fertility is CR’s natural counterpart: where CR asks “how many raw units does one token buy,” fertility asks the mirrored question, “how many tokens does it take to say one word?” — the average number of tokens produced per whitespace-delimited word. Lower fertility is better, for the identical reason higher CR is better: fewer tokens per word means a shorter sequence for the model to process, and shorter sequences are cheaper at every layer of the transformer that consumes them.

The second, Type-Token Ratio (TTR), asks a different question entirely: of all the distinct token types the vocabulary contains, how many actually get used across a real evaluation corpus, relative to the total number of tokens produced? A vocabulary can have 128,000 entries and still spend nearly all of its usage on a small, overworked subset of them — TTR is one way of catching that. It is a close cousin of the “vocabulary utilization” metric you’ll see in Chapter 4’s main table, but measured slightly differently: vocabulary utilization asks what share of the learned merges ever fire on held-out text, while TTR asks about the diversity of tokens actually emitted on a specific corpus. Both point at the same underlying worry — a vocabulary that looks large on paper but is functionally small in practice, because most of its capacity never gets used on the languages that need it.

Hold onto a specific tension for Chapter 4: making the vocabulary fairer, as we’re about to do, does not automatically move every one of these metrics in the “better” direction at once. A merge budget spent chasing the worst-off language is, definitionally, a merge budget spent somewhere the classical objective wouldn’t have spent it — and Chapter 4 shows exactly which of these four metrics move together and which one moves the opposite way you might expect.

Why real implementations don’t rescan the whole corpus every step

The pseudocode above is faithful to the algorithm, but reading it literally would suggest something computationally alarming: at every one of K steps, recount every adjacent pair across the entire corpus from scratch. For K = 128,000 merges over billions of bytes, that naive reading is far too slow to actually run. Production BPE trainers avoid it with a standard trick worth knowing, because you’ll want the same instinct when Chapter 3 modifies this loop: maintain a running count of every pair’s frequency in a priority queue (typically a max-heap), and after each merge, instead of recounting the whole corpus, only update the counts for pairs that touched the exact positions the merge just changed. Every merge invalidates a small, local neighborhood of counts, not the whole corpus — so the total work across all K merges stays close to linear in corpus size, not quadratic in K times corpus size. This is exactly why the “asymptotic complexity is unchanged” claim you’ll meet again in Chapter 3 is a meaningful thing to say: it is talking about this incremental-update structure, not the naive from-scratch rescan the pseudocode implies for readability.

Why 128,000 merges, and not some other number?

K, the merge budget, is a free hyperparameter, and every tokenizer this session compares uses K = 128,000 — a scale that sits comfortably in the range real production multilingual tokenizers actually use, not a number chosen just to make one experiment convenient. It’s worth understanding the trade-off it’s balancing, because Chapter 4 will show that trade-off has real consequences.

A bigger K means more merges, which means higher compression (Chapter 1’s eq. 2) and therefore shorter token sequences for the same raw text — and shorter sequences are cheaper everywhere downstream, because a transformer’s attention computation grows worse than linearly with sequence length. But a bigger K also means a bigger vocabulary 𝒱 (recall eq. from Chapter 1: 𝒱 = 𝗁 ∪ {merges}, so vocabulary size grows one-for-one with merge count), and every entry in that vocabulary needs its own row in the model’s embedding table and its own column in the final softmax that predicts the next token — both of which sit on the critical path of literally every forward and backward pass, not just at tokenization time. Push K too small and sequences get needlessly long; push it too large and the embedding table and softmax become a meaningful fraction of the model’s total parameter count and compute, for diminishing compression returns. 128,000 is the specific point in that trade-off both papers’ experiments hold fixed while they vary the thing that actually matters to this session — not how big the vocabulary is, but whose content it was optimized to compress.

Holding K fixed across every tokenizer variant this session compares is itself a deliberate experimental control worth naming: it means every Gini number, every compression-rate number, and every downstream-accuracy number you’ll see in Chapter 4 isolates the effect of which objective learned the merges, with the vocabulary-size trade-off held constant on both sides of the comparison. If Classical BPE and Parity-aware BPE used different vocabulary sizes, a fairness improvement could be confounded with a simple “more vocabulary slots” effect — and Chapter 4’s separate 256k-vocabulary check exists precisely to confirm the same qualitative pattern holds even once you deliberately change the one variable this comparison otherwise holds fixed.

Chapter 2: The Cross-Lingual Fairness Problem

Chapter 1 ended on a gap: the BPE objective sees bytes, not languages. Now let’s make that gap measurable — first with a formal definition of per-language cost, then with a single number that captures how unequal that cost is across an entire vocabulary of languages.

Per-language compression rate

Let ℒ = {ℓ(1), …, ℓ(R)} be a set of languages, and let each byte-string in the corpus carry a language label. Restricting the corpus-level formula from Chapter 1 (eq. 2) to only the documents labeled ℓ gives a per-language compression rate:

This is the number that actually matters to a user: for a fixed vocabulary, how many tokens does content in their language cost, on average? A service that bills per token, or that has a fixed context window, translates CR(ℓ; τ) directly into dollars or into how much of a conversation fits in memory.

Why raw byte counts are the wrong ruler

Comparing CR(ℓ; τ) across languages sounds simple, but the choice of normalization unit u can quietly bias the comparison. Whitespace-delimited “words” are ill-defined in languages without spaces between words. Even normalizing by raw bytes is biased, because scripts differ enormously in bytes-per-character — ASCII needs one byte per character, while CJK characters typically need three in UTF-8. A language that looks expensive under byte-normalization might just be using a heavier script for the exact same amount of meaning.

The paper’s fix is to use a parallel corpus: text that says the same thing in every language, aligned sentence by sentence (they use FLORES+). Measuring tokens-per-aligned-line normalizes by content instead of by script, so a genuine fairness gap doesn’t get confused with “this script happens to need more bytes.”

FLORES+ (an extension of FLORES-200, originally built for machine translation evaluation) is a useful choice specifically because it was designed with the opposite goal from a training corpus: every sentence is professionally translated by humans, one-to-one, across all supported languages, so line i genuinely says the same thing in every language rather than merely covering the same topic. A training corpus scraped from the web cannot offer that guarantee — the English web crawl and the Amharic web crawl were never written to say identical things line by line — which is exactly why fairness measurement needs a purpose-built parallel resource even though tokenizer training itself can use whatever multilingual data is available.

Worked illustration: how byte-normalization alone can mislead

This example is illustrative, chosen only to make the bias concrete — not a measured number from the paper. Suppose an English sentence is 20 characters long and, since ASCII needs exactly one byte per character, that’s also 20 bytes. Suppose the same sentence, translated into a CJK language, is more information-dense and needs only 10 characters to say the identical thing — but each of those characters, encoded in UTF-8, costs 3 bytes:

Normalize by raw bytes and the CJK sentence looks 50% more “expensive” — 30÷20 = 1.5× — even though it says the exact same thing in half as many characters. The apparent cost gap here is a pure artifact of UTF-8’s byte encoding for CJK scripts, not a real difference in how much content each language is conveying. Normalizing by aligned lines instead — as FLORES+ allows — sidesteps this entirely: both lines represent the same one unit of content, so whatever token-count difference remains after that normalization is attributable to the tokenizer’s actual behavior, not to an encoding accident.

Collapsing many languages into one number: the Gini coefficient

Table 1 later in this session compares six tokenizer variants across eight metrics each — useful for detail, useless as a single “is this fair?” verdict. The paper borrows a tool from economics for exactly that verdict: the Gini coefficient, normally used to measure income inequality across a population, repurposed here to measure token-cost inequality across languages.

Let c1 ≤ c2 ≤ … ≤ cn be the per-language costs (tokens needed per aligned line) for n languages, sorted from cheapest to most expensive. The Gini coefficient of tokenizer T is

Values range from 0 (every language costs exactly the same) to 1 (one language absorbs the entire tokenization budget while the rest are priced out). It looks dense, so let’s compute one by hand before trusting it.

Worked example: computing Gini for three toy languages

Suppose three languages have per-line token costs c = [2, 3, 7] (already sorted, so n = 3). First the two sums:

Next the weighted sum, where language i gets weight (n+1−i) — the cheapest language gets the largest weight, the most expensive gets the smallest:

Plug both sums into eq. 13:

A Gini of 0.28 describes moderate inequality — the most expensive language here costs 3.5× the cheapest. Hold that number in mind: it is the reference point for judging whether the paper’s real, measured numbers in the next two chapters represent a small gap or a large one.

What the real numbers already tell us

Trained on FineWeb2 across 30 languages with a 128k vocabulary, Classical BPE measures Gini = 0.064 on FLORES+ — already noticeably tighter than our illustrative toy above, but still a real, structural gap between the cheapest and most expensive languages in the set. Chapter 4 puts this number next to five parity-aware variants and shows exactly how far each one closes it; for now, the point is just that this gap is measured, not assumed, and it is measured the same way you just computed it by hand.

Consequences, beyond the number itself

The paper is explicit that this bias has two distinct kinds of cost. One is qualitative: “Models trained on fragmented or semantically incoherent tokenizations lose valuable inductive biases and tend to perform worse” — a word chopped into six meaningless pieces gives the model a harder sequence to reason over than the same word represented as one or two coherent chunks. The other is economic and falls directly on users, as we already read in Chapter 0: token-based billing and latency scale with token count, so a worse-compressed language costs its speakers more, every single request.

Where the Gini formula actually comes from

It is worth knowing why the formula in eq. 13 has the specific shape it does, rather than treating it as an arbitrary black box. The classical economic version of the Gini coefficient starts from a picture called the Lorenz curve: sort your population (here, languages) from cheapest to most expensive, then plot the cumulative share of total cost accounted for by the cheapest x% of languages, for every x from 0 to 100. If every language costs exactly the same, that curve is a straight diagonal line — the cheapest 20% of languages account for exactly 20% of total cost, and so on. If one language absorbs almost the entire cost, the curve stays near zero for a long stretch and then shoots up at the very end. The Gini coefficient is defined as twice the area between that curve and the perfect-equality diagonal — a pure geometric measure of how far the real distribution bows away from equal shares. Equation 13’s weighted-sum formula is an algebraically equivalent, discrete way of computing that same area directly from a finite list of costs, without ever having to draw the curve.

Two extremes, worked by hand

It helps to see the formula behave at its two boundary cases before trusting it in the middle. Four languages, all costing exactly the same, c = [5, 5, 5, 5] (n = 4):

Perfect equality gives exactly zero, as the formula promises. Now the opposite extreme — one language absorbing essentially the entire cost, c = [0.01, 0.01, 0.01, 9.97] (still summing to 10, but now wildly skewed):

Nowhere near the true limiting value of 1.0 — because three languages still share a nonzero, if tiny, cost. Push all three of those toward zero and the ratio climbs toward exactly 1. Between these two hand-worked poles — 0.000 for perfect equality, 0.747 for near-total concentration — sits the entire range that real tokenizers occupy: Classical BPE’s measured 0.064 and Parity-aware BPE’s measured 0.007 are both, by this scale, close to the equal end, which is exactly why a casual glance at either number alone can undersell how much the ratio between them (an 89% relative reduction, verified by hand in Chapter 4) actually matters.

A second lens on concentration: Rényi entropy

The Gini coefficient is not the only way the field quantifies “how unevenly is this cost spread out.” The evaluation suite behind this session also reports Rényi entropy, a standard family of entropy measures parameterized by α, computed here over the distribution of per-language costs at α = 2.5. Where Gini answers “how far from equal is this distribution,” Rényi entropy answers a related but distinct question — “how much effective diversity does this distribution have,” treating a distribution concentrated on one or two languages as low-diversity regardless of exactly how the inequality is shaped. On the real 30-language benchmark, both Classical BPE and Parity-aware BPE measure 0.49 on this metric — essentially unchanged. That is a genuinely useful negative result: it tells you the fair-max objective is redistributing which languages are expensive without meaningfully changing the overall shape of the cost distribution’s diversity — the improvement Chapter 4 reports is concentrated precisely in the tail (the worst-off languages), which Gini is sensitive to and this particular entropy measure, at this α, is not.

Rust et al. (2021) is part of why this per-language framing matters beyond an abstract fairness score: their finding was that a tokenizer’s per-language compression is not just a cosmetic statistic — it measurably predicts how well a multilingual model performs in that language downstream. That is the exact throughline Chapter 4 will verify with real accuracy numbers, and it is why this session treats CR(ℓ; τ), not just the aggregate Gini score, as a quantity worth caring about per language, not only in summary.

Why Gini caught the gap that Rényi entropy at α = 2.5 didn’t

That flat 0.49-to-0.49 Rényi reading isn’t a coincidence of this one dataset — it follows from what the α parameter in a Rényi entropy actually controls. As α rises above 1, the entropy formula becomes increasingly dominated by the largest probability masses in the distribution — at the limit α → ∞, it depends on nothing but the single largest mass. At α = 2.5, the measure is already leaning heavily toward the dominant, high-resource languages that make up most of the cost distribution’s mass, and comparatively insensitive to what’s happening in the distribution’s thin tail — exactly where a handful of worst-off languages live. Gini, by contrast, weights every rank position linearly in eq. 13’s formula, so a change concentrated entirely in the cheapest few languages still moves the aggregate score meaningfully. Two entropy-flavored measures, two different sensitivities to the tail — and the fair-max objective’s entire intervention happens to live precisely in the region one of them is built to notice and the other is built to smooth over.

What breaks if you forget to sort first

The sorting step in eq. 13 (“let c1 ≤ c2 ≤ … ≤ cn”) looks like a minor bookkeeping detail, but it’s load-bearing. Take the same three costs from the earlier worked example, [2, 3, 7], but this time apply the rank weights (n+1−i) to them in a different, unsorted order — say [7, 2, 3], as they might arrive straight from a database query with no ordering guarantee:

A negative Gini coefficient is meaningless — the quantity is only ever defined on [0,1]. The formula silently produces nonsense the moment the costs aren’t sorted cheapest-to-most-expensive before the weights are applied, because the weighting scheme (n+1−i) is specifically designed to give the cheapest language the largest weight and the priciest the smallest — applying that same weight pattern to an arbitrary, unsorted order breaks the entire geometric argument the Lorenz-curve derivation rests on. It’s a small implementation detail with an outsized consequence: get it wrong and you won’t get an error, you’ll get a confidently-reported, silently-invalid number.

Chapter 3: Parity-Aware BPE: The Fair-Max Rule

Chapter 1 gave us classical BPE’s objective — maximize global compression (eq. 4). Chapter 2 showed why that global framing produces cross-lingual inequality, measurable as a Gini coefficient. Now we fix it, by changing exactly one thing: what “maximize” means.

The fair-max objective

Instead of maximizing the average (global) compression rate, Parity-aware BPE maximizes the minimum compression rate across all languages:

This is a max-min (sometimes called Rawlsian, after the philosopher John Rawls’s “maximize the position of the worst-off” criterion) objective. It doesn’t ask “which merge helps the most content, on average?” — it asks “which merge helps whichever language is currently worst off?” The paper calls this a fair-max rule, and names its cost plainly: “it trades a small amount of global compression for cross-lingual parity.” We’ll verify in Chapter 4 exactly how small that trade turns out to be.

The algorithm: one change to the inner loop

Parity-aware BPE keeps the entire greedy, step-by-step structure from Chapter 1. Only the pair-selection step changes. At merge step k, first identify the current worst-compressed language, using the tokenizer built so far (τm<k) measured on a development set:

Then apply classical BPE’s own rule — count adjacent pairs, take the most frequent one — but restrict the counting to 𝒟ℓ★, that one language’s slice of the training corpus. The chosen merge, once found, is applied everywhere — across every language’s data, not just ℓ★’s. That last detail is what separates this from simply training separate monolingual tokenizers and gluing their vocabularies together: a merge discovered because it helps the worst-off language might turn out to be useful for other languages too, and this algorithm lets it earn a place in the shared vocabulary regardless.

python
# Algorithm 2: the ONE line that differs from Chapter 1's Algorithm 1 is marked
V = set(range(256))
merges = []

for k in range(K):
    # CHANGED: find the worst-compressed language on the dev set (eq. 6)
    cr = {lang: compression_rate(dev_set[lang], tokenizer) for lang in languages}
    worst_lang = min(cr, key=cr.get)

    # CHANGED: count pairs ONLY within worst_lang's training data
    pair_counts = {}
    for doc in train_corpus[worst_lang]:
        for v, v2 in adjacent_pairs(doc):
            pair_counts[(v, v2)] = pair_counts.get((v, v2), 0) + 1
    best_pair = max(pair_counts, key=pair_counts.get)

    # UNCHANGED: apply the chosen merge to EVERY language's data
    new_symbol = concat(best_pair)
    V.add(new_symbol); merges.append(best_pair)
    for lang in languages:
        train_corpus[lang] = [apply_merge(d, best_pair, new_symbol) for d in train_corpus[lang]]

Illustrative walkthrough: five merges, two ways

Here is a small, hand-built scoreboard — not measured data, purely to make the control flow concrete — for three toy languages A, B, C sharing a merge budget of five. Before any merges, every language sits at the trivial baseline CR = 1.0 (Chapter 1’s eq. 1, with zero tokens saved yet).

Under classical BPE, language A happens to dominate the pooled corpus by sheer volume, so nearly every merge chases A’s most frequent pairs:

Under fair-max, the algorithm above picks the currently worst language at every step, so the merge budget gets spread out rather than piling onto whoever is already ahead:

Final spread under fair-max: 1.55 − 1.30 = 0.25, versus classical BPE’s 0.90 for the identical five-merge budget. Same number of merges, same total “compression work” done — but fair-max spent that work narrowing the gap between languages instead of widening it. This is the mechanism, not a measurement; Chapter 4 shows what it produces on the real 30-language benchmark.

Three variants for three different constraints

The base fair-max rule assumes you have a parallel dev set and want strict equality. Real deployments have different constraints, so the paper defines three configurable variants.

Hybrid. Run classical BPE for the first J merges, then switch to fair-max for the remaining K merges — in the paper’s experiments, J = K, exactly half and half. This captures some of classical BPE’s early, cheap, broadly-useful merges before spending the back half of the budget on parity.

Moving-window balancing. A worst-off language can get “stuck” — its dev set might be too small, or its text might have simply run out of useful merges to make. To stop the algorithm from wasting its whole remaining budget on a language that isn’t actually improving, track the W most recently selected languages and forbid re-selecting one that has already appeared more than α · W ÷ |ℒ| times in that window. The paper uses W = 100, α = 2.

Ratio-normalized (dev-set-free). When no parallel dev set exists — code and math data have no natural “translation” — you can instead specify a target compression ratio rℓ per language directly and select

— the language furthest below its own target, relative to that target, gets picked. This can be computed entirely on the training set, no parallel corpus required.

What this costs, computationally

Relative to classical BPE, the only overhead is recomputing per-language compression rates on the dev set at every merge step — an O(|ℒ|) pass, negligible next to the corpus-wide pair-counting both algorithms already do. Asymptotic complexity is unchanged. And critically: only the learning phase differs. Once the merge list m is fixed, tokenizing new text works exactly as it always did — apply the merges in order. Nothing about inference changes; this is a drop-in replacement at training time only.

Worked example: what the moving-window cap actually allows

The moving-window variant’s two hyperparameters — W = 100 and α = 2 — sound abstract until you plug in the number of languages this session actually studies. On the main 30-language benchmark you’ll see real numbers for in Chapter 4:

In plain terms: no single language is allowed to be picked as “currently worst-off” more than 6 times out of any 100 consecutive merges. Compare that to the uncapped fair-max rule, which could in principle let one stubborn, hard-to-improve language occupy every single slot in that window if its compression rate simply never rises above its rivals’. The cap forces the algorithm to move on to the second-worst language once the cap is hit, even if the original worst-off language is still, technically, worst. On the 60-language ablation from Chapter 4, the identical formula gives 2 × 100 ÷ 60 = 3.33, floored to 3 — a tighter cap, because more languages are competing for the same 100-merge window. This is the same dilution pattern Chapter 4 measures directly in the fairness numbers themselves: more languages sharing a fixed budget means less room for any one of them to dominate, whether that budget is merges or window slots.

Worked example: the ratio-normalized rule with real target ratios

Equation 7’s rℓ is a target compression ratio you specify per language, and the selection rule divides current performance by that target rather than comparing raw compression rates directly. Suppose two languages have current compression rates CRA = 1.60 and CRB = 1.20, so a naive “pick the lowest raw CR” rule (ignoring targets entirely) would call B worse off. Now suppose language A is inherently harder to compress — a heavily agglutinative language, say — so its realistic target is only rA = 1.70, while B’s target, an isolating language with simple morphology, is rB = 2.40:

Ratio-normalization flips the verdict: B is picked, not A, because B is further below its own achievable ceiling even though A has the lower raw compression rate in absolute terms. This is precisely the flexibility the rule buys you when a parallel dev set is unavailable — you don’t need every language to reach the same absolute compression rate, only for each one to close the gap toward whatever target is realistic for that language’s own morphology. The price, as Chapter 4 shows with real measured numbers, is that this flexibility depends entirely on how well-calibrated your chosen targets are — a badly guessed rℓ steers the algorithm toward the wrong language just as confidently as a well-calibrated one steers it toward the right one.

Making “negligible overhead” concrete: how many dev-set evaluations, really?

This chapter called the per-merge overhead of recomputing worst-language compression “an O(|ℒ|) pass, negligible.” It’s worth putting a real number behind that adjective rather than trusting it on faith. At the main benchmark’s scale — 30 languages, 128,000 merges — equation 6 gets evaluated 30 × 128,000 = 3,840,000 times over the whole run. That sounds like a lot until you remember what each individual evaluation actually is: tokenizing and counting tokens across one language’s small development set with the tokenizer built so far — a few hundred to a few thousand lines of text, using a merge list that already exists. Compare that to what the pair-counting step in the very same loop is doing at every one of those 128,000 iterations: scanning a slice of the entire training corpus, which for a real pretraining pipeline is measured in billions of tokens. The dev-set pass touches a rounding error’s worth of text next to the training-corpus pass that both classical and parity-aware BPE already have to do every single step — which is precisely why the paper can say the two algorithms share the same asymptotic complexity and mean it literally, not just approximately.

The hybrid variant, walked through as a budget

The hybrid variant’s J = K split, applied to the real 128,000-merge budget this session uses throughout, means the first 64,000 merges run under classical BPE’s pure global-compression objective, and the remaining 64,000 switch to the fair-max rule. The intuition for why this ordering — classical first, fair-max second — rather than the reverse, is that the earliest merges in any BPE run tend to be broadly useful across nearly every language regardless of which objective picked them: common punctuation, whitespace patterns, and short high-frequency sequences that appear constantly no matter what language you’re looking at. Spending the first half of the budget letting classical BPE grab those cheap, broadly-shared wins costs little in fairness, because early merges tend to help everyone roughly proportionally anyway. The back half of the budget, where languages have already diverged in how well they’re compressing, is where the fair-max objective’s worst-off-first selection has the most room to actually redirect the remaining merges toward whoever needs them most.

Why greedy, worst-language-first, is tractable where a joint search isn’t

It’s worth being explicit about the search space fair-max is navigating, echoing Chapter 1’s point about why classical BPE is greedy in the first place. At each of the K merge steps, fair-max faces exactly |ℒ| candidate “which language is worst off” choices — 30 or 60 in this session’s real benchmarks — and once that choice is made, the specific pair to merge is just classical BPE’s own single-most-frequent-pair rule, restricted to one language’s data. That’s a trivial amount of extra search per step: compare |ℒ| numbers, take the minimum. Contrast that with what a truly optimal fair-max solution would require: jointly choosing the entire ordered sequence of K merges to maximize the true objective in eq. 6, which means searching over merge-list orderings whose count grows combinatorially with K — wildly intractable for K = 128,000. Fair-max, like classical BPE before it, trades that intractable joint optimization for a locally-greedy approximation: optimal at every individual step, with no guarantee (and no attempt) to look ahead at how today’s choice affects which language will be worst-off ten steps from now. The paper doesn’t claim otherwise — the fair-max rule is a greedy heuristic for the fair-max objective, precisely mirroring how classical BPE itself is a greedy heuristic for eq. 4.

Chapter 4: Variants, Ablations, and What They Cost

Time to check the fair-max rule against reality. Everything in this chapter is measured, not illustrative — tokenizers trained on FineWeb2 and mC4, evaluated on FLORES+, exactly as described in Chapters 2 and 3.

Table 1: the headline comparison

128k-vocabulary tokenizers trained on the unbalanced 30-language FineWeb2 dataset (30 languages sampled in their natural, skewed proportions — the realistic setting), evaluated on the matching FLORES+ subset:

Worked example: verifying the headline “89%” claim

The abstract claims “up to an 89% reduction” in the Gini coefficient. Let’s check that arithmetic against Table 1’s own numbers, using the same Gini formula (eq. 13) from Chapter 2:

That matches the abstract exactly. And notice the compression-rate column while you’re there: 0.0275 → 0.0276, a change in the fourth decimal place. The 89% fairness gain cost essentially nothing in aggregate compression — vocabulary utilization even went up, from 67.0% to 70.4%, meaning more of the 128k vocabulary slots are actually earning their keep across languages rather than sitting unused for the languages that were being ignored.

Why the ratios variant reduces Gini the least

Look back at Table 1: every dev-set-based variant gets Gini below 0.02, but the ratios variant only reaches 0.040. The paper attributes this to a domain mismatch. The ratio targets rℓ are derived from FLORES+ bytes-per-line statistics — carefully content-aligned across languages. But the merge-selection statistics that eq. 7 actually optimizes against are computed on FineWeb2, whose genre and domain mix can differ substantially by language. A target built from one distribution, applied to select merges from a different distribution, is a weaker signal than measuring the real thing directly on a dev set — useful when you truly have no parallel data, but not a free substitute for it.

Worked example: does the gain hold as you add languages?

The same experiment on mC4 (a different training corpus) at two scales tells a more nuanced story. With 30 languages:

With the language count doubled to 60:

The fairness gain shrinks — 89% on FineWeb2’s 30 languages, roughly 60% on mC4’s 30 languages, down to roughly 42% on mC4’s 60 languages. This is an honest, reported limitation, not a hidden one: with a fixed merge budget K and more languages competing for the “currently worst off” slot, each language gets fewer turns at the front of the queue, so the ceiling on how much any one language’s compression can be pushed up shrinks. Fairness interventions dilute as the number of groups you’re being fair across grows, for a fixed budget — a pattern worth remembering well beyond tokenizers.

Does fairness cost downstream accuracy?

Intrinsic tokenizer metrics are necessary but not sufficient — the real test is whether a language model trained with the fairer tokenizer still performs. The paper trains 3-billion-parameter LLaMA-architecture decoder-only models on 100 billion tokens of FineWeb2 (tokenizers trained on mC4, temperature sampling τ = 3.3), then evaluates on 12 multilingual benchmarks across 22 languages. A sample of the per-language results (accuracy %, random-chance baseline included for scale):

Across all 22 languages, the hybrid variant shows nominal gains in 14 and nominal declines in 6, and the paper reports that individual differences are generally within standard error — the conclusion is “no evidence that Parity-aware tokenizers would compromise downstream LM performance.” Read the table honestly, though: Persian is a real decline (42.80 → 39.15, one of the six), and Bengali sits essentially at the random-chance floor under every tokenizer — fairer tokenization narrows the cost gap, but it does not by itself manufacture downstream capability where the model simply hasn’t seen enough Bengali text to learn the task. We’ll return to exactly that limit in Chapter 8.

The two metrics Chapter 1 promised, now measured

Chapter 1 flagged fertility and Type-Token Ratio as two more lenses on tokenizer quality, and promised this chapter would show which of them move together with Gini and which one doesn’t. The real numbers, same 30-language FineWeb2 benchmark as Table 1:

TTR moves in the direction you’d hope: a more diverse set of the vocabulary’s token types actually gets used once merge budget stops concentrating on a handful of dominant languages. Fertility, though, moves the wrong way — average tokens-per-word rises by 2.3%, a small but real cost. This is the honest tradeoff underneath the headline “nearly free lunch” framing: spreading merges toward worst-off languages means slightly fewer merges are available to shorten the average word for the languages that were already doing fine, so the corpus-wide average word needs marginally more tokens to spell out, even while the corpus-wide compression rate (measured in bytes, not words) barely moves. Two metrics of the “same thing,” two different verdicts — which is exactly why Chapter 1 warned against trusting any single number in isolation.

What the model is actually being tested on

The 12-benchmark, 22-language downstream suite behind Table 2 isn’t one uniform task repeated in every language — it spans several genuinely different skills, and it’s worth knowing what they are before trusting an aggregate number. Belebele is multilingual reading comprehension: read a short passage, answer a question about it. XNLI is natural language inference: given two sentences, decide whether the second follows from, contradicts, or is neutral toward the first. PAWS-X is paraphrase identification: two sentences that share almost every word — do they mean the same thing? XWinogrande and XCodah probe commonsense reasoning through pronoun resolution and plausible-continuation selection. XStoryCloze asks the model to pick the sensible ending to a short story. MMMLU and EXAMS test multilingual factual and academic knowledge directly, closer to a school exam than a reasoning puzzle. Spreading the evaluation this wide matters precisely because a tokenizer fix could, in principle, help one narrow skill while doing nothing for (or even hurting) another — and the paper’s claim of “no evidence of compromised performance” is only as convincing as the breadth of what it was tested against.

Does the fairness gain survive a bigger vocabulary?

Every number in this chapter so far used a 128,000-entry vocabulary. The paper repeats the same comparison at 256,000 entries — double the merge budget — to check whether the fair-max rule’s benefit is an artifact of a specifically constrained vocabulary size. It isn’t: parity-aware variants continue to outperform Classical BPE on every cross-lingual fairness metric at the larger vocabulary size too. That is a meaningful robustness check in its own right — it rules out the possibility that fair-max only looks good because a small, contested vocabulary happens to force a more even split, and confirms the mechanism (worst-off-language-first selection) keeps working once there is comfortably enough merge budget for every language to plausibly get its fair share.

Where the utilization gain actually landed

Table 1’s vocabulary-utilization column — 67.0% under Classical BPE, 70.4% under Parity-aware BPE — is worth turning into an actual count of vocabulary entries, not just a percentage. Over a 128,000-entry vocabulary:

The paper’s own resource-tier breakdown (Figure 1) explains where those roughly 4,350 entries came from: “Parity-aware tokenizers provide more consistent usage across languages, evening out the vocabulary allocation to high vs. low resource languages in comparison to Classical BPE.” Under Classical BPE, a meaningful share of the 128,000 learned merges are essentially dead weight for low-resource languages — entries that only ever fire on the high-resource languages that dominated the merge selection in the first place, while low-resource text falls back to shorter, less efficient sub-merges or raw bytes. Parity-aware BPE’s worst-off-first selection means more of those 128,000 slots earn their keep across the whole language set, which is the mechanistic reason vocabulary utilization rises even though the vocabulary size itself never changed.

The downstream result, stated as precisely as the paper states it

Chapter 4’s earlier downstream table showed a sample of six languages out of the full 22; it’s worth reporting the paper’s own summary statistic across the complete set rather than eyeballing a sample. Models trained with the hybrid variant show a median per-language change in accuracy of +0.19 percentage points, with 14 of the 22 languages improving and 6 declining (the remaining 2 essentially flat). A median of +0.19pp is a genuinely small number — smaller than most of the individual per-language standard errors reported alongside it — which is exactly the quantitative basis for the paper’s “no evidence of compromised performance” conclusion. It is a small, mostly-positive shift with real exceptions, not a uniform win across the board, and reporting the median rather than cherry-picking a favorable mean is itself a marker of how carefully this comparison was run.

Is this a BPE-specific problem, or does every subword algorithm have it?

It’s worth being honest about scope here rather than overreaching. The paper’s own introduction names the broader family this problem belongs to: “the predominant tokenization algorithms — such as Byte Pair Encoding and UnigramLM — construct the vocabulary by maximizing frequency-based objectives.” UnigramLM is a genuinely different mechanism from BPE — instead of greedily merging pairs upward from bytes, it starts from a large candidate vocabulary and iteratively prunes the subwords that contribute least to a probabilistic likelihood objective. What both algorithms share, despite that mechanical difference, is exactly the property Chapter 1 identified as the root cause: a single, language-blind, frequency-based objective computed over the pooled corpus. Chapter 1’s critique of classical BPE’s eq. 4 — that it has no notion of “language” and simply rewards whichever content contributes the most raw frequency — is a structural critique of the objective family, not of BPE’s specific merge mechanics. This session should be precise about what that implies and what it doesn’t: the paper builds and empirically validates the fair-max fix specifically on top of BPE, because BPE is what the large majority of production LLM tokenizers actually use, and it does not run the equivalent experiment on UnigramLM. The theoretical argument for why a frequency-pooling objective produces unfairness plausibly extends beyond BPE; the 89% measured reduction this session verified by hand does not, on its own, tell you anything about UnigramLM specifically.

Reading a results table like this one, as practice

Table 1 rewards a specific reading habit worth naming explicitly, since it recurs constantly in ML papers: scan for the metric that’s supposed to move, confirm it moved by the claimed amount (this chapter verified the 89% Gini reduction by hand), then scan every other column for anything that moved in an unexpected direction, and ask whether that unexpected movement is small enough to ignore or large enough to qualify the headline claim. Applied here: Gini dropped as claimed (the expected win), compression rate barely moved (an expected, and reassuring, non-effect), vocabulary utilization rose (an unexpected but welcome bonus, explained mechanistically earlier in this chapter), and fertility rose slightly (an unexpected, small, honestly-reportable cost). Four columns, three different verdicts, and only one of the four is the headline number most people would quote from memory. Reading past the single number a paper leads with, into the rest of its own table, is the difference between citing a result and understanding it.

Chapter 5: Data Mixing as an Optimization Problem

We now leave tokenization behind and pick up the second upstream lever from Chapter 0: how much of each data source the model actually trains on. Even with a perfectly fair tokenizer in hand, someone still has to decide this — and as Chameleon’s introduction puts it plainly, “the composition of these datasets significantly influences the generalization capabilities and downstream performance of LLMs.”

Formalizing the problem

Suppose your data lake is organized into k distinct domains 𝒟 = {D1, …, Dk} — these could be sources (arXiv, GitHub, Wikipedia, a web crawl) or, just as naturally, languages. The goal is to find a domain weight vector α ∈ Δk, where Δk is the probability simplex — every αi ≥ 0 and they sum to 1 — that maximizes how well the resulting model generalizes.

The earliest approach was manual: favor sources that look high-quality by inspection, like Wikipedia and academic text. The paper is blunt about the limitation: “while intuitive, these approaches are neither optimal nor scalable.” There is no principled way to hand-tune 7, let alone 22, weights against a moving downstream target.

The proxy-model approach, and its two leading methods

Modern domain-reweighting methods share a two-stage strategy: train a small, cheap proxy model to infer good domain weights, then train the large, expensive base model using those weights. This works because — and multiple studies have confirmed it — domain weights transfer reasonably well across model scales; a weight vector tuned on an 82-million-parameter proxy still helps a 1.2-billion-parameter base model, as we’ll verify with real numbers in Chapter 7.

Two established methods drive the proxy’s optimization differently:

Both work, and both are expensive in a way that compounds with the number of domains. DoGE’s per-iteration cost against a plain training step grows with k: roughly 1.7× wall-clock at 7 domains, and roughly 2.5× wall-clock once you scale to 17 domains, because every additional domain is one more gradient to compute every step.

The deeper problem: both methods are brittle to change

Here is the failure mode that motivates Chameleon specifically. Both DoReMi and DoGE derive their domain weights from the proxy model’s optimization process — its loss trajectory, or its gradients, accumulated over thousands of training steps. That process is entangled with the exact data the proxy saw. The moment your data changes — a new source arrives, an existing domain gets split into finer categories, a language is added — the old optimization trace is no longer valid, and there is no way to patch it. You must retrain a new proxy model from scratch and rerun the entire optimization.

For a live, evolving data pipeline — which is what every real pretraining pipeline actually is — this is a serious practical tax. Chameleon’s introduction states its design requirements explicitly, and they read as a direct response to this brittleness: an ideal method should

1. (i) improve universal generalization — the basic goal of domain reweighting;
2. (ii) adapt to domain modifications, because data naturally evolves between preparation and training and frequent recalibration is impractical;
3. (iii) handle different training stages — both pretraining and fine-tuning, where most existing methods only handle the former.

The core design choice: optimization process vs. the data itself

Chameleon keeps the same two-stage strategy — small proxy, then large base model — for a fair comparison against DoReMi and DoGE. What changes is what the proxy is used for. Instead of watching how the proxy struggles to fit each domain (its loss, its gradients), Chameleon simply uses the proxy as a feature extractor: run each domain’s data through it, average the resulting hidden representations, and ask a purely geometric question about those representations — how redundant or unique is each domain relative to the others, in the space the proxy already understands?

This is the entire reason Chameleon can sidestep the retraining problem. The proxy’s weights never need to change when new data arrives — you just run the new data through the same already-trained proxy, get new embeddings, and recompute the geometric quantity. No optimization loop to rerun.

the two philosophies, side by side
# DoReMi / DoGE: weights come from watching the proxy TRAIN
proxy = train_with_group_dro(domains, weights=uniform)  # or track_gradients(...)
weights = extract_from_optimization_trace(proxy)     # entangled with THIS training run
# new domain arrives -> must retrain proxy from scratch

# Chameleon: weights come from embedding the DATA once training is done
proxy = train_small_model(domains, weights=uniform, steps=2000)  # trained once
embeddings = [proxy.embed(domain) for domain in domains]   # one forward pass each
weights = leverage_scores(embeddings)              # pure geometry, Ch. 6
# new domain arrives -> just embed it with the SAME proxy, no retraining

What “small proxy” and “large base model” actually mean, in parameters

“Small” and “large” are doing a lot of work in that sentence, so it’s worth pinning down the real architectures Chapter 7 will run. The proxy is a genuinely small transformer: 82 million parameters, 6 layers, 12 attention heads, a 768-dimensional embedding, and a 3,072-dimensional feed-forward hidden layer — trained for only 2,000 steps. Compare that to what DoReMi and DoGE spend on their own proxy training: roughly 10,000 steps, five times as many, because their weight-extraction method needs the proxy’s optimization trajectory to actually unfold and stabilize, not just its representations to settle.

The base model that eventually consumes those weights is far larger. The main experiment in Chapter 7 trains a 684-million-parameter model — 36 layers, 24 attention heads, a 1,200-dimensional embedding, a 4,800-dimensional feed-forward hidden layer — roughly 8.3× the proxy’s parameter count. The scale-up experiment later in Chapter 7 goes to 1.2 billion parameters: the same 36 layers, but 25 attention heads and a wider 1,600-dimensional embedding with a 6,400-dimensional hidden layer — roughly 14.6× the proxy. Both training runs share the same optimizer hyperparameters as the proxy (batch size 128, weight decay 0.01, gradient clipping at 1.0), differing mainly in learning rate: the proxy trains at a peak learning rate of 5×10−4, while the base models use a gentler 1.5×10−4, standard practice for larger models that need smaller steps to stay stable.

Notice what this buys, concretely: an 82M-parameter model training for 2,000 steps is orders of magnitude cheaper to run than an 8×-to-15×-larger base model training for however many steps the full pretraining run takes. The entire economic case for the two-stage strategy — compute a cheap signal once, reuse it on the expensive run — rests on that size and step-count gap being real and large, which these numbers confirm it is.

DoReMi and DoGE, by name and by result

It’s worth knowing these two baselines as real, independently-published methods, not just as foils for Chameleon. DoReMi — “Optimizing Data Mixtures Speeds Up Language Model Pretraining” (Xie, Pham, Dong, Du, Liu, Lu, Liang, Le, Ma & Yu, NeurIPS 2023) — was itself a real advance when it shipped: against a baseline using the Pile’s default, hand-set domain weights, the paper reports DoReMi improves average few-shot downstream accuracy by 6.5 percentage points and reaches that baseline’s accuracy using 2.6× fewer training steps. DoGE — “Domain Reweighting with Generalization Estimation” (Fan, Pagliardini & Jaggi, ICML 2024) — followed, removing DoReMi’s need for a separate reference model by tracking per-domain gradients directly during proxy training instead.

This context matters for reading Chapter 7 honestly. Chameleon is not being measured against two strawmen — DoReMi and DoGE are both real, published, competitive methods that meaningfully beat naive uniform mixing in their own right. The claim this session is building toward isn’t “domain reweighting matters, and here’s proof” (DoReMi already proved that in 2023); it’s the narrower, sharper claim that Chameleon gets a comparable or better result at a small fraction of what those two already-good methods cost to run.

The two-stage strategy, made concrete as configuration

Concept-and-realization means being able to point at the actual objects a formula refers to, not just the formula. Here is what “train a small proxy, then train a large base model with the resulting weights” looks like as an actual training configuration, using the real architecture numbers from above:

python
# Stage 1: the proxy -- small, cheap, trained just long enough to embed the data well
proxy_config = {
    "layers": 6, "heads": 12, "d_model": 768, "d_ffn": 3072,
    "params": "~82M", "steps": 2000, "lr": 5e-4, "batch_size": 128,
}
proxy = train(proxy_config, domains, weights=uniform)

# the ONLY thing the base model inherits from the proxy is a length-k weight vector
weights = compute_domain_weights(proxy, domains)   # Chameleon / DoReMi / DoGE differ ONLY here

# Stage 2: the base model -- 8x to 15x larger, trained on the real budget, with real weights
base_684M_config = {
    "layers": 36, "heads": 24, "d_model": 1200, "d_ffn": 4800,
    "params": "~684M", "lr": 1.5e-4, "batch_size": 128,
}
base_model = train(base_684M_config, domains, weights=weights)  # full pretraining run

Everything upstream of the compute_domain_weights line — the architectures, the training loop, the optimizer — is identical no matter which reweighting method you use. Every real difference between DoReMi, DoGE, and Chameleon lives entirely inside that one function call: what it reads from the proxy, and how much compute it costs to compute its answer. Chapter 6 opens that function up.

Why the simplex constraint pushes toward a softmax

Recall the formal target from earlier in this chapter: a weight vector α ∈ Δk, the probability simplex — every entry non-negative, all entries summing to exactly 1. Any raw score a method computes — a loss, a gradient norm, a leverage score — has no reason to already satisfy either property. Losses and gradient norms are strictly positive but don’t sum to 1; leverage scores are bounded but not guaranteed positive-and-summing-to-1 either. You need some function that maps an arbitrary vector of real-valued scores onto the simplex, and softmax — exp(si) ÷ ∑j exp(sj) — is the standard choice for a specific reason: it’s guaranteed positive (exponentials are always positive, regardless of the sign of the input score), guaranteed to sum to 1 by construction (the denominator is exactly the sum of the numerators), and it preserves the ranking of the input scores — a higher raw score always produces a higher weight, since exp is monotonically increasing. That last property matters: it means the actual work of Chapter 6’s KRLS formula is done entirely by producing a good ranking of domains, and softmax’s only remaining job is converting that already-correct ranking into a valid probability distribution — it doesn’t need to know anything about tokenization, domains, or leverage scores to do that job correctly.

What actually happens when a domain gets added mid-project

Chapter 5’s design requirement (ii) — adapt to domain modifications without frequent recalibration — is easiest to see concretely by walking through what each method literally has to do when your data lake gains an eighth domain partway through a project that started with seven. For DoReMi: the reference model and the proxy model were both trained under Group DRO against the original seven-domain simplex; adding an eighth domain changes the dimensionality of that simplex itself, so both models need to be retrained from scratch against the new eight-domain objective — there is no partial-update path. For DoGE: the same problem, for the same reason — its per-domain gradient tracking was set up for seven domains, and extending it to an eighth means re-running proxy training with the gradient-tracking machinery reconfigured for the new domain count. For Chameleon: the proxy’s weights never referenced “seven domains” anywhere — it only ever produces embeddings from whatever text you feed it. Adding an eighth domain means embedding a batch of its examples with the same, already-trained proxy, appending one new row and column to the 7×7 affinity matrix to make it 8×8, and re-running the cheap O(k3) KRLS computation — now on k=8 instead of k=7. Nothing about the proxy itself changes; only the small matrix it feeds into does.

Chapter 7’s Pile-transfer experiment is exactly this scenario, scaled up from a hypothetical eighth domain to an entirely new dataset with an unrelated set of domains: SlimPajama’s 7 domains give way to the Pile’s 17, and the affinity matrix grows from 7×7 to 17×17 — still just a matrix inversion over a two-digit dimension, still cheap, still using the identical proxy that was never retrained. Everything this chapter just walked through in the abstract, Chapter 7 measures in real FLOPs.

What 2,000 proxy steps actually processes

It’s easy to let “2,000 steps” slide past as an abstract hyperparameter; multiplied out against the batch size from earlier in this chapter, it becomes a concrete amount of data:

A quarter of a million examples is enough for an 82-million-parameter model to form a reasonable representation of what each domain’s content looks like — enough to embed usefully, in Chapter 6’s sense — without needing anywhere near the volume of data or steps a full pretraining run would require to actually reach strong absolute performance. That gap is the entire economic argument for this chapter’s two-stage strategy in one number: the proxy never has to be good at language modeling in any absolute sense, it only has to be good enough that its internal representations meaningfully separate the domains it has seen.

Chapter 6: Chameleon: Leverage Scores Over Domain Embeddings

Chapter 5 left one precise question open: given a proxy model and a set of domains, how exactly do you turn “how redundant is this domain relative to the others” into a number? This chapter builds that number from scratch, then a toy example you can verify by hand.

Step one: a domain embedding is just an average

For each domain Di, take a sizeable random batch of its examples, run each one through the proxy model, and average the resulting L-th layer hidden vectors:

where hθp(L)(a) is the proxy’s L-th-layer representation of example a. The result, xi ∈ ℝp, is the centroid of that domain in the proxy’s representation space — a single vector that summarizes “what this domain’s content typically looks like, according to the proxy.” Stack all k domain embeddings into a matrix X = [x1, …, xk]⊤ ∈ ℝk×p.

Step two: a domain affinity matrix

Define similarity between two domains with the simplest possible kernel — a plain dot product: κ(xi, xj) = xi⊤xj. Stack all pairwise similarities into the domain affinity matrix:

Why a plain linear kernel, and not something fancier with nonlinear features? The paper’s own reasoning is a concept-and-realization moment worth sitting with: “we employ the linear kernel as the LM itself already introduces significant non-linearity.” The proxy’s many transformer layers have already done the nonlinear feature-extraction work by the time you reach layer L; bolting a second nonlinear kernel on top would just add hyperparameters to tune without adding real expressive power.

Step three: Kernel Ridge Leverage Scores

Ω𝒟 tells you how similar every pair of domains is, but not yet how important any single domain is on its own. For that, the paper reaches for Kernel Ridge Leverage Scores (KRLS), a tool from kernel ridge regression that answers exactly this question: how much does domain i contribute something that the other domains, together, cannot already reconstruct?

This is the i-th diagonal entry of the “hat matrix” from kernel ridge regression, with regularization strength λ > 0 and identity matrix I. High Sλ means the domain is unique — hard to approximate as a combination of the others. Low Sλ means the domain is well-represented — easily reconstructed from the rest, sharing broad, common characteristics. As a limiting case the paper states directly: “if a row (domain) has a component orthogonal to all other rows (domains), its leverage score is 1” — total uniqueness, maximum score.

Worked example: redundancy lowers the score, by hand

Two clean two-dimensional toy cases, both with k = 2 domains and λ = 0.5 (so kλ = 1, keeping the arithmetic tidy).

Case 1 — independent domains. Let x1 = [1, 0], x2 = [0, 1] (orthogonal). Then Ω𝒟 = I, so Ω𝒟 + I = 2I, and

Case 2 — identical (fully redundant) domains. Let x1 = x2 = [1, 0]. Now Ω𝒟 = [[1,1],[1,1]], and Ω𝒟 + I = [[2,1],[1,2]], with determinant 2·2 − 1·1 = 3, so

Independent domains scored 0.500 each; identical, fully-redundant domains scored only 0.333 each. Making the two domains redundant with each other pulled both of their individual scores down — exactly the direction the theory promised. Redundancy is punished, uniqueness is rewarded, and now we have the arithmetic to prove it rather than just assert it.

Turning scores into weights: the phase-specific inversion

Here is Chameleon’s single cleverest move. Pretraining and fine-tuning want opposite things from this score, so the paper simply inverts it between the two phases, then applies a softmax to turn scores into a proper probability distribution:

The theoretical justification is that the inverse KRLS, Sλ−1, is proportional to the Christoffel function — a standard measure of how dense a region of embedding space is. High density (many domains clustered together, each easily reconstructed from the others) means a high inverse score, which pretraining rewards, because dense regions represent general-purpose, broadly-useful knowledge — exactly what a base model should spend most of its budget learning. Fine-tuning flips the logic: you’re specializing, so you want the domains that carry information the rest of the mixture doesn’t already provide, which is precisely what a high raw KRLS score identifies.

Back to our toy: in Case 1 (independent), both inverse scores are 1 ÷ 0.5 = 2.0 — equal, so softmax gives each domain 50% either way, which makes sense: two fully independent domains give the pretraining objective no reason to prefer one over the other. In Case 2 (identical), both inverse scores are 1 ÷ 0.333 = 3.0 — also equal to each other, but larger in absolute terms than Case 1’s 2.0. Two identical toy domains can’t show you an asymmetry between themselves, only that redundant pairs, as a category, get pulled toward a stronger inverse-score signal than independent pairs. Seeing weights actually differ between two unequal domains needs three or more domains — which is exactly the real experiment in Chapter 7.

A third, unique domain enters: redundancy dilutes even further

One more hand-checkable case bridges the two-domain toys above to the real seven-domain experiment in Chapter 7. Add a third domain, still 2-dimensional: x1 = [1,0], x2 = [1,0] (identical to x1, a redundant pair, exactly as in Case 2), and now a new x3 = [0,1] (orthogonal to both, fully unique). With k = 3 domains and the same λ = 0.5, the regularization term kλI grows to 1.5I:

This matrix is block-diagonal — domain 3 doesn’t interact with domains 1 and 2 at all, since their dot product is zero — so it inverts as two independent pieces: a 2×2 block with determinant 2.5×2.5 − 1×1 = 5.25, and a trivial 1×1 block. Working through the matrix product Ω𝒟(Ω𝒟+1.5I)−1 and reading off the diagonal:

Compare this to the pure two-domain Case 2 from earlier, where the identical redundant pair scored 0.333 each. Adding a third, unrelated domain pulled the redundant pair’s score down further, from 0.333 to 0.286, even though nothing about domains 1 and 2’s own relationship to each other changed. That is the regularization term kλ doing its job as designed: as the total number of domains competing for representational space grows, the bar for “genuinely unique” rises, and a pair that was merely redundant with each other now reads as even more redundant once measured against a bigger, more varied field. This is precisely the dilution mechanism that lets a real 7-domain affinity matrix (Chapter 7) meaningfully separate a broad, overlapping domain like a general web crawl from a narrow, distinctive one like preprint mathematics — the more domains you throw into the mixture, the more sharply the redundant ones get told apart from the unique ones.

python
import numpy as np

X = np.array([[1.0, 0.0], [0.0, 1.0]])   # Case 1: independent domain embeddings
k, lam = 2, 0.5
Omega = X @ X.T                                # domain affinity matrix
H = Omega @ np.linalg.inv(Omega + k*lam*np.eye(k))
S = np.diag(H)                          # S = [0.5, 0.5]  <- matches the hand computation

alpha_pt = np.exp(1/S) / np.exp(1/S).sum()   # pretraining: softmax(inverse KRLS)
alpha_ft = np.exp(S) / np.exp(S).sum()          # fine-tuning: softmax(KRLS)

Connecting the toy to the real data

Chameleon’s own visualization of real domain embeddings (a UMAP projection of SlimPajama, described in the paper) reports exactly this pattern in the wild: “broad domains like ‘CC’ and ‘C4’ create dominant regions, covering shared semantic space, while more specific domains like ‘Arxiv’ are more distinct.” CC and C4 behave like our redundant toy pair — correlated, overlapping, individually low-KRLS — while Arxiv behaves like an independent, higher-KRLS domain. Chapter 7 shows exactly what that predicts for the real pretraining weights, and it matches.

What this costs, computationally

Given the domain affinity matrix, computing KRLS is an O(k3) matrix inversion — cheap, because k is the number of domains (7 to 22 in the experiments you’ll see in Chapter 7), never the number of documents. The only per-example cost is a single forward pass through the small proxy to get its embedding. No gradients, no backward pass, no optimizer state — embedding extraction is pure inference.

Does the weight depend on which proxy you happened to train?

A fair worry about any method that routes its answer through one specific small model: what if a differently-sized or differently-sampled proxy gives a meaningfully different weight? The paper runs exactly this check, holding everything else fixed and varying one factor at a time. Real Arxiv-domain weights across four proxy sizes:

Worked out, the full spread across a nearly 3.5× range of proxy sizes:

A 12% swing across a proxy size range that itself spans 3.5× is a mild, not alarming, sensitivity — the weight is clearly influenced by which proxy computed it, but not dramatically reshuffled. The paper reports the same pattern — weights staying in a narrow band — across all seven SlimPajama domains, and repeats the check for the regularization strength λ (values 1, 10, and 100 give Arxiv weights of 0.080, 0.083, and 0.087 respectively — again a narrow band) and for how many examples get embedded per domain (2,000, 4,000, and 8,000 samples give 0.079, 0.083, and 0.081 — essentially flat past a few thousand samples). None of Chameleon’s three main hyperparameters — proxy size, λ, or sample count — is load-bearing in the sense of swinging the answer wildly; the method is measuring something real about the data, not an artifact of one particular hyperparameter choice.

Stability across training steps: the real number behind Chapter 5’s claim

Chapter 5 argued that DoReMi and DoGE are entangled with a specific optimization trace, while Chameleon isn’t. Here is the measurement that backs that claim up. Tracking the Arxiv domain weight at an early proxy checkpoint (1,000 steps) against a fully-trained one (10,000 steps):

Chameleon’s weight for this domain barely moves across nine thousand additional training steps of the proxy. DoReMi’s drops by more than three-quarters over the identical stretch — meaning if you had stopped DoReMi’s proxy training early to save compute, you would have gotten a qualitatively different answer about how important the Arxiv domain is. That instability is the direct, measured consequence of deriving weights from an optimization trace that hasn’t yet converged, exactly as Chapter 5 predicted: DoReMi’s excess-loss signal is still actively changing while the proxy is still learning, so when you stop training the proxy quietly becomes part of the answer. Chameleon’s embeddings settle almost as soon as the proxy has learned enough to represent the data reasonably — which is also exactly why 2,000 steps is enough for it, while DoReMi and DoGE need roughly five times as many just to reach a trustworthy reading.

The Christoffel function, one more time, in plain terms

The paper’s own gloss on the inverse-KRLS-as-density connection is worth quoting directly, because it is the single sentence that explains why inverting the score is the right move for pretraining specifically, not an arbitrary trick: “during pretraining, assigning higher sampling probability to domains with high Sλ−1 upweights high-density data regions, which are most influential on base LMs’ performance.” Read that plainly: a base model’s job is to build a broadly competent, general-purpose representation of language, and the regions of representation space with the most mass — the densest, most redundant, most “everyone agrees this matters” regions — are, almost by definition, the regions most influential to getting that general competence right. A domain sitting in a sparse, isolated region of embedding space might be fascinating and specialized, but it simply doesn’t represent as much of what a base model needs to get broadly right. Fine-tuning inverts the logic for the opposite reason: once you already have general competence, the domains worth extra attention are exactly the sparse, distinctive ones the base phase didn’t prioritize.

Chapter 7: The Mixture Showcase (real numbers, end to end)

Chapter 6 built the machine. This chapter runs it on the paper’s real experiment — SlimPajama-627B, 7 domains, an 82-million-parameter proxy, a 684-million-parameter base model — and every number below is measured, not illustrative.

Real domain weights: SlimPajama, 7 domains

Uniform weighting would give every domain 1 ÷ 7 ≈ 0.143. Here is what Chameleon actually computes, next to the two expensive baselines it’s competing with:

Chameleon’s weights sum to 1.0, as required. Look at CC and C4 — the two broad, overlapping domains from Chapter 6’s UMAP quote — they take 0.202 + 0.247 = 0.449, nearly 45% of the whole mixture, exactly as the low-KRLS, high-inverse-KRLS story predicted.

Worked example, real numbers. Compare individual weights to the uniform baseline of 0.143:

Wikipedia getting downweighted might look surprising — it’s usually treated as “high quality” text. But KRLS isn’t measuring quality; it’s measuring how much of Wikipedia’s representational content is already covered by the other six domains combined. That’s a genuinely different question from “is this text well-written,” and the whole point of a data-centric method is that it answers the question it was actually asked.

Does the reweighting actually help? Perplexity, checked

Per-domain held-out test perplexity for the 684M base models (lower is better):

Chameleon posts the best average perplexity of all five methods — including RegMix, a baseline that gets to cheat by knowing the downstream target domain in advance. Worked out:

What it cost to get there

This is the number that actually distinguishes Chameleon — not that it wins, but what winning costs. Reported FLOPs to obtain the domain weights, relative to Chameleon’s own cost:

And in GPU-hours to obtain the weights, next to the 56 GPU-hours the 684M base model itself takes to train:

Chameleon adds roughly a tenth of the overhead that either baseline adds, while producing the best perplexity of the four downstream-agnostic methods. The paper phrases this as reducing “computational overhead to less than 2% of final training cost” — our hand calculation of 1.4% confirms it.

Transfer without retraining: SlimPajama proxy, applied to the Pile

Here is the scenario Chapter 5’s design requirement (ii) was built for. Take the exact proxy already trained on SlimPajama, and point it at the Pile dataset instead — 17 available domains (the original 22, minus 5 removed for copyright reasons), most of them domains the proxy has never seen a weight computed for. DoReMi, DoGE, and RegMix all have to retrain a fresh proxy from scratch on Pile’s domain composition. Chameleon just runs 4,000 samples per new domain through the same, unchanged proxy and recomputes KRLS.

Verify the headline ratio by hand:

And Chameleon isn’t just cheap here — it also has the best perplexity of all four methods, beating even the manually-curated Human baseline the original Pile paper used, at a fraction of a percent of the retraining cost the other automated methods require.

Worth verifying that “beats the human baseline” claim by hand rather than taking it on faith, since it’s the more surprising of the two claims in this table:

That is a genuinely notable result to sit with: a fully automated method, computed from an 82-million-parameter proxy’s embeddings with no human judgment involved at any step, outperforms domain weights that a team of researchers hand-picked using their own expert sense of which sources matter and how much. It doesn’t mean human judgment is worthless — it means human-set weights, however thoughtfully chosen, are still a guess at the same underlying quantity KRLS computes directly: how redundant or unique each domain’s content actually is, relative to the rest of the mixture.

Scale check: does it hold at 1.2B parameters?

Domain weights from the 82M proxy, applied to a base model 15× larger:

The improvement doesn’t just survive the scale-up — the paper reports it gets slightly larger, consistent with the general finding that domain weights transfer across model sizes.

Fine-tuning: the mirror image

Chapter 6’s two formulas differ only in whether the score is inverted. Fine-tuning uses the direct KRLS, favoring unique domains over broad ones. Fine-tuning the Pile-pretrained model 10k steps on two very different target sets, comparing uniform weighting to Chameleon’s αFT:

Every single domain in both fine-tuning sets improved — no exceptions, in either direction of the same underlying score.

It isn’t just perplexity — downstream tasks agree, at both scales

Held-out perplexity is a proxy for “does the model fit the data well,” but the number that ultimately matters is task performance. At the 684M scale, averaged across the same downstream-task suite used elsewhere in this session, Chameleon reaches 39.6% average accuracy — the best of the four methods compared, with DoGE close behind at 39.4% and DoReMi and Uniform further back. At the 1.2B scale you already saw in the perplexity comparison, the accuracy gap widens rather than closes:

Notice DoReMi and DoGE actually trade places between the two metrics — DoGE has better perplexity than DoReMi (16.26 vs 17.17) but slightly worse downstream accuracy (40.4 vs 40.5), a reminder that perplexity and task accuracy, while correlated, are not the same objective and can disagree in the details. Chameleon is the only method that leads on both metrics, at both scales, which is a meaningfully stronger claim than leading on either one alone.

What RegMix actually is, and why it costs so much more

RegMix (Liu, Zheng, Muennighoff, Zeng, Dou, Pang, Jiang & Lin, ICLR 2025) has come up several times in this chapter as “a baseline that gets to cheat by knowing the downstream target in advance,” and it’s worth knowing exactly how it earns that description. RegMix doesn’t train one proxy — it trains many: the original paper reports fitting a regression model on 512 separate models, each roughly a million parameters, each trained on a different, randomly-sampled data mixture, for a billion tokens apiece. That regression then predicts which mixture will perform best, and the predicted winner gets scaled up to the real training run. Treating mixture selection as a literal regression-fitting problem over hundreds of small training runs is powerful — RegMix does sometimes win on a specific benchmark it was tuned toward — but the cost scales with how many candidate mixtures you sample, which is exactly why the FLOPs table earlier in this chapter shows RegMix at 9× Chameleon’s cost on SlimPajama and a striking 758× on the Pile transfer, where all 512 proxy runs have to be redone from scratch for the new dataset just as DoReMi and DoGE do. Chameleon’s single proxy, embedded once, is answering a structurally cheaper question than “which of hundreds of candidate mixtures regresses best against a target metric.”

Reading Chameleon’s own summary of itself

It’s worth closing this chapter with the paper’s own framing of what it built, in its own words: “training data mixtures greatly impact the generalization performance of large language models. Existing domain reweighting methods often rely on costly weight computations and require retraining when new data is introduced. To this end, we introduce a flexible and efficient data mixing framework, Chameleon, that employs leverage scores to quantify domain importance within a learned embedding space.” Every number this chapter measured — the 7.8% average perplexity reduction over uniform, the roughly 10× and 5× compute savings over DoReMi and DoGE, the 290× savings on an unretrained transfer to a new dataset, and the fact that it leads on both perplexity and downstream accuracy at two different model scales — is a direct, measured cashing-out of that one-sentence claim.

Chapter 8: Where Tokenizer and Mixture Meet

Both papers now stand on their own. Neither mentions the other — Parity-aware BPE never discusses domain weights, and Chameleon’s domain embeddings are computed after some tokenizer already exists, because the proxy model has to turn text into tokens somehow before it can embed anything. But they sit in series on the exact same training run, and understanding how they multiply against each other is the payoff of covering both in one session.

Two independent knobs on the same budget

Recall the compression rate identity from Chapter 1, rearranged:

And the tokens budgeted to any domain or language ℓ is set by the mixture weight: tokens budgeted to ℓ = αℓ × total training tokens. Substituting:

Two independent multipliers act on the same total training-token budget: the tokenizer’s per-language compression rate CR(ℓ; τ), decided once by Parity-aware BPE or its classical alternative, and the mixture weight αℓ, decided by Chameleon or its alternatives. If either multiplier is small, the amount of actual content a language receives during training is small — no matter how generous the other one is.

Two failure modes, worked through

Failure mode 1: a perfect tokenizer, a bad mixture. Suppose your tokenizer achieves the paper’s best measured Gini of 0.007 — near-total token-cost parity. If the data mixture still allocates only 0.5% of the token budget to some language, the model sees almost nothing of it regardless. Cost-per-token parity says nothing about total exposure; those are genuinely different quantities, and only one of them is what Parity-aware BPE was built to fix.

Failure mode 2: a perfect mixture, a bad tokenizer. Suppose Chameleon allocates a generous mixture weight to a low-resource language’s domain — say, matching a well-resourced language’s weight exactly. If the underlying tokenizer is Classical BPE with a real measured Gini of 0.064, that language’s content is still fragmented into disproportionately more tokens per unit of meaning. The same token allocation buys strictly less actual text, because CR(ℓ; τ) is smaller for that language.

Worked example: the two multipliers, together

This example uses illustrative, not measured, per-language compression numbers — the real ones live in FLORES+ curves the papers plot but don’t tabulate as text — chosen only to make the multiplication concrete and consistent with the real magnitude of the effect from Chapter 4.

A 100-billion-token run allocates a low-resource language αℓ = 0.01 (1% of the mixture):

Under Classical BPE, suppose that language’s compression rate is illustratively CR = 1.2 content-units per token (poor, near the low end of the real spread in Fig. 2 of the tokenizer paper). Under Parity-aware BPE, its compression rate improves to CR = 1.8 — a 50% improvement, roughly consistent with the tightened per-language spread Chapter 4 measured:

For the identical mixture weight — Chameleon or DoReMi or Uniform, doesn’t matter which — the fairer tokenizer alone delivers 50% more actual content to that language, for free, because the token-to-content exchange rate improved. The two papers’ interventions genuinely compose: fixing the tokenizer helps even if the mixture never changes, and fixing the mixture helps even if the tokenizer never changes, but fixing both compounds multiplicatively rather than just adding.

An honest caveat: these two papers’ real experiments don’t share a domain axis

Before going further, one nuance is worth stating precisely rather than glossing over. Parity-aware BPE’s real, measured experiment (Chapters 2–4) partitions its corpus by language — 30 languages, each with its own CR(ℓ; τ). Chameleon’s real, measured experiment (Chapters 6–7) partitions SlimPajama by source type — Arxiv, Book, CC, C4, GitHub, StackExchange, Wikipedia — predominantly English text sorted by where it came from, not by what language it’s written in. So you cannot literally take Table 1’s per-language compression rate and multiply it against Chapter 7’s per-source domain weight; those are two different real experiments, sliced along two different axes, and neither paper runs the experiment that would combine them directly. The worked example just below is therefore explicitly illustrative — built to show how the arithmetic would combine in a pipeline where the domain axis and the language axis coincide, which is exactly what happens in practice whenever “domain” is defined as “language,” a completely standard choice in multilingual pretraining and one both papers explicitly allow. The compounding logic is real and general; the specific numbers in the worked example below are chosen to be consistent with the real magnitude of effect Chapter 4 measured, not read off a single joint experiment either paper actually ran.

A subtlety worth one more paragraph: the proxy inherits the tokenizer too

Chameleon’s domain embeddings come from a proxy language model — and that proxy has to tokenize its inputs with some tokenizer before it can embed anything. If that upstream tokenizer is unfair across languages, and domains happen to be defined by language, a badly-fragmented language’s text arrives at the proxy already shredded into many small, low-information tokens. Whether that measurably distorts the resulting domain embedding — making a poorly-tokenized language look artificially “blander” or more redundant than it truly is, purely as a tokenization artifact rather than genuine semantic overlap — is not something either paper tests directly, since neither treats the other paper’s problem as in scope. It is exactly the kind of interaction worth being suspicious of whenever you stack two independently- developed pipeline stages: each was validated holding the other one fixed at whatever the field’s default happens to be.

What running both interventions costs, together

It’s worth closing the loop on cost, not just benefit, since Chapter 0 opened on a training budget and this session has tracked overhead carefully at every step. Parity-aware BPE’s overhead is paid once, during tokenizer training, and is measured in complexity terms rather than GPU-hours: an O(|ℒ|) bookkeeping pass per merge step, on top of pair-counting work Classical BPE was already doing. Tokenizer training itself runs over raw text on CPUs, not GPUs, and finishes long before the GPU-hour-denominated base-model training run even starts — so its added cost doesn’t compete for the same expensive hardware Chapter 7’s 56 GPU-hour figure is measuring. Chameleon’s overhead, by contrast, is paid on the same GPU cluster as the base run and is exactly the 1.4% measured in Chapter 7. Stack the two: the combined pipeline’s added GPU-hour cost, relative to a naive Classical-BPE-plus- Uniform-mixture baseline, is still dominated entirely by Chameleon’s 1.4%, because the tokenizer’s overhead was never competing for GPU time in the first place. Fairness on both axes, in other words, costs about the same as fairness on one of them — the mixture side’s overhead, since that’s the only one that touches the expensive hardware at all.

The order of operations, and why it can’t run the other way

A real pipeline that wants both interventions has exactly one valid ordering, and it’s worth being explicit about why. Parity-aware BPE has to run first, end to end, before Chameleon’s proxy model ever sees a single example — because, as the subtlety above already established, the proxy has to tokenize its inputs with some tokenizer before it can embed anything, and that tokenizer has to already exist. You cannot run them concurrently or in the opposite order: there is no version of Chameleon that computes domain embeddings from raw, untokenized bytes, and there is no version of Parity-aware BPE that needs domain weights to learn a vocabulary. This isn’t a design choice either paper made independently — it falls directly out of what each algorithm consumes as input. The full, correct pipeline for a project that wants both fixes reads: learn the tokenizer on the full multilingual corpus first (Chapters 1–4), then train the small proxy on that already-tokenized corpus and compute domain weights (Chapters 5–7), and only then start the actual base-model pretraining run, which consumes both outputs simultaneously, every single step (Chapter 0’s pipeline pseudocode).

A practitioner’s checklist

Distilled into decisions an engineer actually has to make, in the order they have to make them:

1. Do you have a parallel dev set across your languages? If yes, use base fair-max or the moving-window variant (Ch. 3); if no, fall back to the ratio-normalized variant and budget for its weaker Gini reduction (Ch. 4).
2. Is your merge budget shared across a large number of languages? If so, temper your expectations for how much any single language’s compression can improve — the 89% reduction was measured at 30 languages, not 60 (Ch. 4).
3. Do your domains change between when you prepare the data and when you train? If yes, this is exactly the scenario DoReMi and DoGE handle badly and Chameleon was built for (Ch. 5, design requirement ii).
4. Are you pretraining or fine-tuning? The single sign flip between αPT and αFT (Ch. 6) means the same KRLS computation answers both questions — just double-check which formula you’re actually calling.
5. Have you checked whether your upstream tokenizer might be distorting your domain embeddings? Neither paper tests this interaction directly (Ch. 8) — it is the one gap in this session worth treating as an open question on your own pipeline, not a solved one.

The full pipeline, annotated end to end

Putting every real number from this session into one script makes the composition concrete in a way prose alone can’t. This is the entire upstream pipeline, using the real hyperparameters and architectures this session actually measured:

python
# STAGE 1 (Ch. 1-4): learn the vocabulary, once, on the full raw corpus.
# Real scale: 30 languages, FineWeb2, K=128_000. Runs on CPU, finishes before any GPU is touched.
tokenizer = learn_bpe(
    corpus=raw_multilingual_corpus, K=128_000,
    objective="fair_max", dev_set=flores_plus_dev,   # eq. 6, Ch. 3
    variant="hybrid+window", W=100, alpha=2       # Ch. 3's two guardrails
)   # -> Gini 0.064 -> 0.007 on this benchmark (Ch. 4), measured after training finishes

# STAGE 2 (Ch. 5-7): tokenize the corpus with the NOW-FIXED tokenizer, train a small proxy,
# and compute domain weights from its embeddings. Real scale: 82M params, 2,000 steps.
tokenized_corpus = [tokenizer.encode(doc) for doc in domain_corpus]
proxy = train(proxy_config, tokenized_corpus, weights=uniform)  # 6L/12H/768d, lr=5e-4
embeddings = [proxy.embed(domain) for domain in domains]    # Ch. 6, x_i = mean hidden state
weights = softmax(inverse_krls(embeddings, lam=10))       # pretraining phase -> alpha^PT

# STAGE 3 (Ch. 0's original loop): the actual pretraining run consumes BOTH outputs.
# Real scale: 684M or 1.2B params. This is the ONLY stage that touches the big GPU cluster.
for step in range(num_steps):
    domain = sample_domain(weights)          # decision 2, from Stage 2
    tokens = tokenizer.encode(sample_text(domain))  # decision 1, from Stage 1
    train_step(base_model, tokens)

Read top to bottom, the three stages are exactly the three phases this session covered in order: Stage 1 is Chapters 1 through 4, Stage 2 is Chapters 5 through 7, and Stage 3 is the loop Chapter 0 first wrote down before either fix existed. Every number annotated in the comments above — the Gini reduction, the proxy size, the step count — is a real, measured value from earlier in this session, not a placeholder.

Where each intervention shows up if you go looking for it later

One last practical point before the closing chapter: if you inherit a pretraining pipeline you didn’t build and want to check whether either fix is already in place, you won’t find a flag named fair_max=True sitting in a config file necessarily — you have to look at the artifact each stage actually produces. For the tokenizer, that means checking whether the merge list itself was learned with a per-language dev set in the loop at all, which usually means checking the training script’s logs or documentation for any mention of per-language compression tracking during vocabulary learning — the tokenizer file alone, once trained, looks identical either way, since Chapter 3 already established that only the learning phase differs, never the encoding function. For the mixture, that means checking whether the domain-sampling weights in the training config are literally uniform, or were computed by some upstream script — and if computed, whether that script needed a full model training run to produce them (DoReMi/DoGE-shaped) or just a handful of forward passes through an already-trained small model (Chameleon-shaped). Both checks come down to the same instinct restated one more time: look at what a stage actually depended on to produce its output, not just what the output looks like once it exists.

What this chapter did and did not claim

Worth being precise on the way out of this chapter, since “the two fixes compose” is a strong enough claim that it deserves a careful boundary. This chapter established, with real measured numbers, that fixing the tokenizer and fixing the mixture are independent levers — each one measurably helps on its own, neither one substitutes for the other, and the compression-rate-times-mixture-weight identity shows precisely how they combine multiplicatively rather than redundantly. What this chapter did not establish, because neither paper actually ran the joint experiment, is a single measured number for “how much better is Parity-aware BPE plus Chameleon, together, than either one alone, on one real training run.” That specific joint measurement is the one honest gap in this session’s evidence — the composition logic is airtight and follows directly from each paper’s own definitions, but the composed number is this session’s own extrapolation, not a citation.

Chapter 9: Evaluation, Failure Modes & Connections

One last pass, this time as a practitioner deciding whether either method is trustworthy enough to ship. Both papers evaluate honestly, including where their own methods fall short — that honesty is worth modeling explicitly before closing the session.

Where Session 01 sits in the pretraining pipeline

Zoom out one more time before the final review. This session covered exactly two of the several decisions a full pretraining pipeline has to make, and it’s worth being explicit about what sits immediately upstream and downstream of the two chapters’ worth of work covered here, so the boundary doesn’t get mistaken for the whole picture. Upstream of everything in this session sits data collection and quality filtering — deciding what enters the raw multilingual corpus at all, before either the tokenizer or the mixture ever sees it; get that stage wrong and neither of this session’s fixes can recover from it, because both fair-max and Chameleon operate on whatever corpus they’re handed. Downstream of everything in this session sits the actual base-model training run itself — the loop from Chapter 0’s pipeline pseudocode, which consumes the tokenizer and the mixture weights this session built but never revisits either one. Further downstream still sits post-training: instruction tuning, preference optimization, and deployment, all of which inherit the tokenizer’s vocabulary permanently (Chapter 0’s opening claim, now fully justified) and inherit whatever the base model actually learned from the mixture this session’s methods computed. Two decisions, two chapters’ worth of formulas, sitting at one specific, narrow, but structurally irreversible point in a much longer pipeline.

In the authors’ own words

It’s worth reading each paper’s own summary of itself once more, back to back, now that every term in both sentences has been built from scratch. Parity-aware BPE, from its abstract: standard tokenizer training “can lead to disparities in users’ costs and experiences depending on language choice,” and the fair-max rule “trades a small amount of global compression for cross-lingual parity,” yielding “an 89% reduction in the Gini tokenizer inequality coefficient compared to Classical BPE.” Chameleon, from its own abstract: “existing domain reweighting methods often rely on costly weight computations and require retraining when new data is introduced,” and its leverage-score framework is offered as a “flexible and efficient data mixing framework” that “employs leverage scores to quantify domain importance within a learned embedding space.” Every chapter in this session, in one direction or another, has been unpacking exactly what those two sentences mean and whether the evidence backs them up. It does, with the honest caveats this chapter is about to lay out plainly.

Notice, reading both abstracts back to back, that neither paper opens by claiming a completely novel problem — both open by naming a well-known, already-costly problem (unfair tokenization; costly, brittle mixture weighting) and then claim a specific, cheaper mechanism for solving it. That is a useful pattern to recognize in how strong empirical ML papers are typically framed: the contribution is rarely “we noticed this matters,” because in a mature field like pretraining, most things that matter have already been noticed by someone. The contribution is almost always “here is a specific, checkable mechanism, and here is the number that shows it works, cheaply, in practice.” Both papers in this session follow that shape exactly, and both numbers — the 89% Gini reduction, the 1.4% compute overhead — are the checkable part.

How to evaluate tokenizer fairness

How to evaluate data mixing

Failure modes, stated honestly

1. Dev-set domain mismatch (Ch. 4). The ratio-normalized variant of Parity-aware BPE loses most of its fairness gain when its reference ratios come from a different corpus distribution than the one it’s actually optimizing — a fairness signal is only as good as how well it matches the real training data.
2. Getting stuck (Ch. 3). Fair-max can repeatedly select a language whose dev set is too small or has exhausted useful merges, without actually improving — which is exactly why the moving-window variant exists as a guardrail, not a nicety.
3. Tokenizer fairness ≠ downstream capability (Ch. 4). Bengali sat at the random-chance floor under every tokenizer variant tested, including the fairest. Equal token cost does not manufacture task competence where the model simply hasn’t seen enough content in that language — which loops directly back to the mixture problem in Chapter 5.
4. Task-aware baselines can win narrowly (Ch. 7). RegMix sometimes beats Chameleon on the specific downstream task it was tuned against, but loses on average perplexity and costs 9× the compute — a reminder that optimizing for one known target and optimizing for broad generalization are different goals with different failure surfaces.
5. Inherited bias (Ch. 8). Chameleon’s domain embeddings depend on a proxy model that itself depends on some upstream tokenizer. Neither paper tests whether an unfair tokenizer distorts Chameleon’s embeddings — a real gap between the two literatures, not a solved problem.
6. A hard floor beneath the fairness objective (Ch. 3). BPE cannot compress a text past the length of its own pre-tokenized sequence — if a language’s tokenizer output is already close to that floor, any BPE variant, parity-aware or not, has diminishing room left to improve it. When this happens under the moving-window variant specifically, the algorithm’s own response is to relax the parity objective rather than force further, unproductive merges — meaning some residual cross-lingual disparity is a structural floor of the method, not a bug to be tuned away.
7. Where a parallel dev set is missing entirely. The base and window variants of fair-max both depend on a small aligned dev set to measure which language is currently worst-off. In domains with no natural parallel data — code, math, or highly domain-specific text — the ratio-normalized variant is the only option, and Chapter 4 already showed it recovers the least fairness of the family precisely because its target ratios and its optimization statistics come from different corpora.

What the authors themselves flag as unfinished

Both papers are candid, in their own closing sections, about what their method does not yet solve — worth reading directly rather than inferring. Parity-aware BPE’s authors write that “while we consider 60 languages and two vocabulary sizes, the interplay between tokenization parity and model scaling still needs to be explored for much larger models, larger language sets, and for code or multimodal inputs,” and separately flag that “fairness in this work is defined purely in terms of token counts” — morphological alignment is measured as a secondary check, but other notions of fairness remain unaccounted for. They also point to a concrete next step for the pre-tokenization floor above: integration with an approach like SuperBPE, which relaxes the whitespace pre-tokenization boundary itself, as a way to give disadvantaged languages more room to compress rather than hitting a hard floor early.

Chameleon’s authors, in their own conclusion, name two directions of their own: extending the method to online settings, where domain weights would update dynamically as training itself progresses rather than being fixed once before the base run starts, and extending the KRLS computation to target a specific downstream task directly, by modifying the identity-matrix regularization term inside the leverage-score formula rather than treating every domain’s uniqueness as equally relevant to every possible use case. Neither extension exists yet in the version of Chameleon this session covers — both are stated explicitly as future work, not quiet gaps you have to infer.

Every hand-worked number from this session, in one place

Nine chapters produced a lot of by-hand arithmetic. Before the final cheat sheet, here is every headline number this session derived or verified by hand, gathered as a single review pass — useful as a study sheet, and a good check that you can still reproduce each one from the formula alone.

Cheat sheet

Notation map: symbol to plain English

Glossary: every term from this session, in one place

Connections

This session built BPE from the ground up; for the transformer that consumes the resulting tokens, see CS224N Lecture 14: Tokenization and Multilinguality and the standalone Tokenization gleam. For the original BPE-for-NMT paper that started subword tokenization in NLP, see the BPE for NMT (Sennrich 2016) veanor. For a complementary, earlier measurement of the same cross-lingual cost gap this session quantified with the Gini coefficient, see the Tokenization Cost (Ahia 2023) veanor. And for a from-scratch look at how pretraining corpora get built in the first place, see CS336: Tokenization Overview.

Chapter 0 traced Parity-aware BPE’s lineage back to three diagnostic papers worth knowing by name if you work on multilingual tokenization: Ahia, Meister, Bosselut et al. (2023), “Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models,” which first quantified the per-token billing disparity across languages; Petrov, La Malfa, Torr & Bhatt (2023), “Language Model Tokenizers Introduce Unfairness Between Languages,” which measured the same fragmentation gap across a wider set of commercial tokenizers; and Rust, Pfeiffer, Vulić, Ruder & Gurevych (2021), “How Good Is Your Tokenizer? On the Monolingual Performance of Multilingual Language Models,” which connected fragmentation to downstream task performance directly. Parity-aware BPE (Foroutan, Meister, Paul, Niklaus, Ahmadi, Bosselut & Sennrich, ACL 2026) and Chameleon (Xie, Tonin & Cevher, ICML 2025) are this session’s two algorithmic answers to that diagnostic literature — the point where measuring the problem turned into fixing it.

Back to the scenario this session opened with

Chapter 0 handed you a 100-billion-token budget, a fixed cluster, and a raw multilingual data lake, and asked you to make two decisions before a single gradient step could run. Nine chapters later, here is the answer this session actually built, in full: learn the vocabulary with the fair-max rule instead of chasing global compression alone, spending roughly the same merge budget but redirecting it toward whichever language is currently worst-compressed at every step, at a bookkeeping cost too small to show up in your training-cluster bill. Then compute domain weights not by watching a proxy model struggle through thousands of optimization steps, but by embedding each domain once and asking a clean geometric question about how redundant it is relative to the rest — at roughly 1.4% of what the base run itself costs, and without needing to redo any of that work the next time a new source shows up in your data lake. Neither decision is a hyperparameter you can tune away after the fact, which is exactly why both had to be solved before Chapter 0’s training loop ever started, and exactly why this session spent nine chapters building each one from a formula, not a slogan.

Carry two specific instincts out of this session, past the two papers themselves. First: whenever a pipeline stage’s objective function is described as maximizing an average, ask what it does to the worst-off element of whatever it’s averaging over — that single question is what turned Chapter 1’s classical BPE into Chapter 3’s fair-max rule, and it generalizes to almost any pipeline stage that pools heterogeneous data into one aggregate number. Second: whenever a method’s cost is described as “retrain when the data changes,” ask specifically what has to be retrained and why — Chapter 5 through 7’s entire case for Chameleon rested on locating exactly which part of DoReMi and DoGE’s computation was entangled with a specific optimization trace, and replacing only that part with something that doesn’t need to change. Both instincts point at the same underlying habit: read past what a method reports, into what it actually depends on.