Tokenization at Scale

"They told me I was a preprocessing step. Then they handed me thirty trillion characters and asked for them back by Tuesday, evenly chopped, nicely packed, with no wasted space."

A Tokenizer That Was Promised It Would Be Quick

The previous section deduplicated and quality-filtered the raw corpus into a clean text dataset. That dataset is still text, and a transformer cannot read text. Between the clean corpus and the first training step sits a translation: every document must be rewritten as a sequence of integer token IDs drawn from a fixed vocabulary, and those sequences must be reshaped into the uniform fixed-length blocks the training loop expects. It is tempting to treat this as a one-line call to a library and move on, and for a small dataset that is exactly right. At corpus scale the picture changes. Tokenizing tens of trillions of tokens is a job whose runtime is measured in thousands of core-hours, and how you pack the result decides how much of your accelerator budget is spent learning versus spent multiplying by zeros. Tokenization is where data engineering and model compute meet, and getting it wrong is expensive in both.

We proceed in three moves. First, what a subword vocabulary is and how it is learned from a sample. Second, why vocabulary size and tokenizer quality, captured by a single number called fertility, ripple through context length and training cost. Third, the distributed mechanics: tokenization as a parallel map, and sequence packing as the step that removes padding waste before the token shards reach the loader.

1. Why Subwords, and How a Vocabulary Is Learned Beginner

A tokenizer needs a vocabulary: a finite set of units, each with an integer ID, that together can represent any input text. Two naive choices bracket the design space and both fail. A word-level vocabulary (one ID per distinct word) is simple but cannot represent words it never saw during construction, and a web corpus has an effectively unbounded word count once you include names, code identifiers, typos, and every language on Earth. A character-level vocabulary (one ID per character) can represent anything but makes sequences brutally long, since a single English word becomes five or six tokens, and sequence length drives transformer cost quadratically in attention. The accepted compromise is subword tokenization: a vocabulary of common character sequences, so that frequent words become a single token while rare words gracefully decompose into a handful of meaningful pieces. Nothing is ever unrepresentable, because the vocabulary always retains the individual characters as a fallback.

Three algorithms dominate. Byte-pair encoding (BPE) starts from individual characters and repeatedly merges the most frequent adjacent pair into a new symbol, growing the vocabulary one merge at a time until it reaches a target size; this is the scheme behind the GPT family. WordPiece, used by BERT, merges by a likelihood criterion rather than raw frequency. The Unigram language model, the default in the SentencePiece toolkit, instead starts from a large candidate vocabulary and prunes it down to the subset that best explains the corpus under a probabilistic model. They differ in detail but share the same two-phase structure that matters for distribution: a training phase that learns the vocabulary from a sample, and an application phase that uses the frozen vocabulary to encode the full corpus.

Because the application phase is stateless and per-document, it parallelizes the same way the MapReduce word count of Section 6.3 did: broadcast the frozen tokenizer to every worker, hand each worker a slice of the input files, and let them emit token shards independently with no communication between them. We will make that structure explicit in Section 3. First, the cost.

2. Vocabulary Size and Fertility: The Cost Knobs Intermediate

Two related quantities decide how much a given tokenizer costs you. The first is the vocabulary size $V$, the number of distinct tokens, which is a hyperparameter you choose (modern models sit between roughly 32,000 and 256,000). The second is fertility: the average number of tokens the tokenizer emits per word (or, language-neutrally, per unit of raw text). Fertility is not a free parameter; it is an outcome of how well the vocabulary matches the text. A vocabulary tuned on English will shatter Hindi or Thai or a stream of source code into many short pieces, inflating fertility on exactly the data you may care about most.

Fertility matters because a transformer's compute and memory are budgeted in tokens, not in words or characters. If tokenizer A needs $1.6$ tokens per word and tokenizer B needs $2.4$ for the same text, then B consumes $50\%$ more sequence positions to express the same content. That has three consequences at once. The same fixed context window holds less actual information, since more of it is spent on fragmentation. The same training compute budget, denominated in tokens by the scaling laws of Section 19.2, covers less real text. And inference costs more per useful character produced. A blunt way to state it: fertility is a multiplier on every token-denominated cost in the system, so a one-time investment in a better-matched vocabulary pays a recurring dividend across the entire training and serving life of the model.

The relationship between vocabulary size and fertility is a trade-off. A larger $V$ lowers fertility, because more words fit in a single token, but it enlarges the embedding and output-projection matrices (each row is a $d$-dimensional vector, so they cost $V \times d$ parameters) and spends model capacity on rare tokens that appear too seldom to learn well. Writing fertility as $f$ and the raw text as $C$ words, the model processes

and the design goal is to push $f$ down (cheaper sequences) without pushing $V$ so high that the embedding tables and rare-token waste dominate. For multilingual or code-heavy models the honest fix is not a single global vocabulary stretched thin but a vocabulary trained on a representative mixture of all the target languages and code, so that no single domain pays a punishing fertility tax. This is why the tokenizer training sample, small as it is, must mirror the language and domain distribution of the full corpus.

3. Tokenization as an Embarrassingly Parallel Map Intermediate

Now the distributed core. Once the vocabulary is frozen, encoding the corpus has the cleanest possible parallel structure: it is a map with no reduce. Split the clean corpus into shards (the same shards your storage layer already exposes), broadcast the small tokenizer artifact to every worker, and let each worker stream its shard through the encoder, writing out a shard of token IDs. Workers never talk to each other, there is no shuffle, and a failed shard is simply re-run, exactly the fault-tolerance story of MapReduce in Section 6.3. The diagram in Figure 19.5.1 shows the full path from text shards to packed sequences, with the parallel tokenize step in the middle and the packing step we build next on the right.

The often-overlooked cost lives in that middle column. Each worker runs a non-trivial encoder over every byte it owns, and "every byte" across a frontier-scale corpus is tens of trillions of characters. This is not a preprocessing afterthought you can fold into the first training epoch; it is a standalone distributed batch job, frequently run once and cached, whose output (the token shards) becomes the real input to training. Treating it as such, with its own scheduling, retries, and monitoring, is what separates a pretraining pipeline that starts on time from one that spends its first day watching a single-threaded tokenizer crawl through the dataset.

The remaining waste is at the boundaries. Documents have ragged lengths, but the training loop wants uniform fixed-length sequences. Pad each document up to the sequence length and you spend a large fraction of every batch on padding tokens that produce no gradient signal: pure wasted compute. Sequence packing fixes this by concatenating tokenized documents end to end, inserting an end-of-document (EOD) marker between them, and then slicing the long stream into fixed-length windows. Almost every position now carries real content; only the final partial window needs any padding at all. The EOD markers let the model (and the attention mask) tell where one document ends and the next begins, so that document-boundary masking can prevent attention from leaking across two unrelated documents that happen to share a packed sequence.

The runnable demo below carries all three ideas end to end in pure Python with no external libraries. It trains a tiny BPE tokenizer on a small sample, applies it to a corpus as a map over four shards (the parallel pattern, executed serially here for reproducibility), reports the resulting fertility, and then compares padded against packed token utilization on the same tokenized documents.

import re
from collections import Counter

# ---- 1. Train a tiny BPE tokenizer on a small SAMPLE ----------------------
sample = ("distributed training scales the model across many machines "
          "the model reads many tokens and the tokenizer maps text to tokens "
          "data parallel training reads sharded data and trains the model "
          "many machines train one model on many tokens of text data ") * 40

def get_words(text):                       # word -> freq; words end with 
    freq = Counter(text.split())
    return {tuple(list(w) + [""]): c for w, c in freq.items()}

def count_pairs(vocab):
    pairs = Counter()
    for symbols, c in vocab.items():
        for i in range(len(symbols) - 1):
            pairs[(symbols[i], symbols[i + 1])] += c
    return pairs

def merge(vocab, pair):                     # fuse one adjacent pair everywhere
    out = {}
    for symbols, c in vocab.items():
        new, i = [], 0
        while i < len(symbols):
            if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
                new.append(symbols[i] + symbols[i + 1]); i += 2
            else:
                new.append(symbols[i]); i += 1
        out[tuple(new)] = c
    return out

NUM_MERGES = 80
vocab, merges = get_words(sample), []
for _ in range(NUM_MERGES):                 # greedy most-frequent-pair merges
    pairs = count_pairs(vocab)
    if not pairs: break
    best = max(pairs, key=pairs.get); merges.append(best); vocab = merge(vocab, best)

# ---- 2. Encode any word by replaying merges in learned order --------------
merge_rank = {pair: i for i, pair in enumerate(merges)}
def encode_word(word):
    symbols = list(word) + [""]
    while True:
        best = best_rank = best_i = None
        for i in range(len(symbols) - 1):
            r = merge_rank.get((symbols[i], symbols[i + 1]))
            if r is not None and (best_rank is None or r < best_rank):
                best, best_rank, best_i = (symbols[i], symbols[i + 1]), r, i
        if best is None: break
        symbols = symbols[:best_i] + [best[0] + best[1]] + symbols[best_i + 2:]
    return symbols
def encode(text):
    out = []
    for w in text.split(): out.extend(encode_word(w))
    return out

# ---- 3. Tokenize a CORPUS as a parallel-style map over shards -------------
docs = ["distributed training reads many tokens",
        "the tokenizer maps text data to tokens",
        "many machines train one model",
        "data parallel training scales the model",
        "the model reads sharded data of text",
        "tokens of text feed the training data loader",
        "scaling laws relate compute and tokens",
        "one model many machines many tokens"]
NUM_SHARDS = 4
shards = [docs[i::NUM_SHARDS] for i in range(NUM_SHARDS)]       # round-robin split
def tokenize_shard(shard_docs):              # a "worker": independent, no comms
    return [encode(d) for d in shard_docs]
shard_results = [tokenize_shard(s) for s in shards]            # the map
tokenized_docs = [doc for r in shard_results for doc in r]     # concatenate

# ---- 4. Sequence packing vs naive padding ---------------------------------
SEQ_LEN, EOD = 16, ""
padded_real = sum(len(t[:SEQ_LEN]) for t in tokenized_docs)
padded_seqs = len(tokenized_docs)
padded_slots = padded_seqs * SEQ_LEN
stream = []
for t in tokenized_docs: stream.extend(t + [EOD])             # pack with EOD markers
packed_seqs = [stream[i:i + SEQ_LEN] for i in range(0, len(stream), SEQ_LEN)]
packed_slots = len(packed_seqs) * SEQ_LEN

print(f"vocabulary size       : {len({s for w in get_words(sample) for s in w} | {a+b for a,b in merges})} subword tokens")
total_tokens = sum(len(t) for t in tokenized_docs)
print(f"fertility (tok/word)  : {total_tokens / sum(len(d.split()) for d in docs):.3f}")
print(f"padded  : {padded_seqs} seqs, util {padded_real / padded_slots:.1%}")
print(f"packed  : {len(packed_seqs)} seqs, util {len(stream) / packed_slots:.1%}")
print(f"sequences saved       : {padded_seqs - len(packed_seqs)} "
      f"({1 - len(packed_seqs)/padded_seqs:.0%} fewer)")

vocabulary size       : 103 subword tokens
fertility (tok/word)  : 1.640
padded  : 8 seqs, util 57.8%
packed  : 6 seqs, util 93.8%
sequences saved       : 2 (25% fewer)

The numbers in Output 19.5.1 are small because the corpus is a toy, but the ratios are exactly the lever that matters at scale: moving utilization from the high fifties to the low nineties means roughly a third fewer training sequences for the identical content, which is a third less wall-clock and accelerator cost spent reaching the same token budget. Multiply that across a run that processes trillions of tokens and packing alone repays its modest engineering cost many times over.

Two practical notes complete the picture. First, the packed token shards are the artifact the rest of training consumes, so they live in the same sharded, sequentially streamable layout the data loader expects; the handoff to Section 8.6 is direct, with no further reshaping. Second, document-boundary masking is not optional politeness: without it, the model would learn spurious dependencies between the tail of one document and the head of an unrelated one that share a packed window, quietly degrading quality in a way that is hard to diagnose later.

4. Reaching for the Library Beginner

Code 19.5.1 is a teaching implementation, deliberately written from scratch so the mechanics are visible. In production you would never hand-roll a BPE trainer: the mature toolkits are fast (Rust-backed), handle Unicode normalization and byte-level fallbacks correctly, and serialize to a single portable artifact you can broadcast to every tokenization worker. The shortcut below trains a comparable tokenizer in a handful of lines.

# pip install tokenizers
from tokenizers import Tokenizer, models, trainers, pre_tokenizers

tok = Tokenizer(models.BPE())
tok.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=True)
trainer = trainers.BpeTrainer(vocab_size=32000, special_tokens=["<eod>"])

tok.train(files=["corpus_sample.txt"], trainer=trainer)   # train on a SAMPLE
tok.save("tokenizer.json")                                 # one portable artifact

ids = tok.encode("distributed training at scale").ids      # apply to a document

# SentencePiece equivalent (Unigram or BPE), also one artifact:
# import sentencepiece as spm
# spm.SentencePieceTrainer.train(
#     input="corpus_sample.txt", model_prefix="tok",
#     vocab_size=32000, model_type="unigram")

With the corpus now a stream of packed, document-masked token shards, every upstream data concern is settled: the dataset is cleaned, deduplicated, tokenized, and packed into the exact fixed-length blocks the training loop ingests. What remains is to drive that token stream through a distributed training run, coordinating thousands of accelerators, checkpoints, and restarts over weeks of wall-clock. That orchestration is the subject of Section 19.6.