Tokenization

A neural network multiplies numbers. Text is not numbers. Before a single parameter gets involved, something has to decide how to chop "The cat sat on the mat." into pieces and which integer each piece becomes. That something is the tokenizer, and it is the most underrated component in the whole pipeline: it is fixed before training starts, it never learns, and yet it shapes what the model finds easy and hard for the rest of its life.

The core question of this chapter is simple. What should the pieces be? The three obvious answers (characters, words, bytes) each fail in an instructive way, and the fix, byte-pair encoding, is an algorithm you can run on paper. Let's start with why the obvious answers fail.

The problem: what should a "piece" of text be?

Whatever the pieces are, the model will keep one embedding vector per distinct piece (the next chapter) and will have to process every piece in the sequence one at a time. So the choice trades off two costs: the size of the vocabulary and the length of the sequence.

Why not characters?

Characters are tempting: a tiny vocabulary (a few hundred symbols), nothing is ever unknown, and spelling is transparent. The catch is length. English averages roughly 4.7 letters per word plus a space, so a 1,000-word passage is about 5,700 characters. Every one of those becomes a position the model must attend over. Since attention cost grows with the square of the sequence length (see the attention chapter), five times the tokens means roughly twenty-five times the attention compute, and the model also has to spend its early layers just reassembling letters into words before it can do anything interesting.

Why not words?

Words are the other obvious unit, and early neural language models used them. Two things break. First, the vocabulary is unbounded: English alone has hundreds of thousands of word forms, then there are names, typos, code identifiers, URLs, and every other language. A fixed table cannot hold them, so anything outside the table becomes a single "unknown" token, and the model literally cannot see it. Second, words share structure that a word-level vocabulary throws away: "unhappiness", "happy" and "unhappily" are separate, unrelated entries, so what the model learns about one does not transfer to the others.

Bytes: the universal fallback

Every piece of text on a computer is a sequence of bytes (UTF-8, in practice). There are exactly 256 possible byte values. So a vocabulary of 256 byte tokens can represent anything: any language, any emoji, any binary junk, with no unknown token ever. This is the property we want to keep. The problem is the same as with characters, only worse: a Chinese character is three bytes, an emoji four. We need a way to keep bytes as the guarantee while making common things cheap.

Byte-Pair Encoding from scratch

BPE was invented as a data compression trick (Gage, 1994) and adapted for neural machine translation by Sennrich et al. (2016). The training algorithm is short enough to state in full.

Notice what is not in the algorithm: no notion of linguistics, no dictionary, no meaning. It is pure frequency counting. That is a strength (it works on any language and on code) and, as we will see, the source of many odd behaviours.

A fully worked example

Let's train on a five-word corpus: low lower lowest newer wider, each word once. We use characters as base symbols and append _ to mark the end of each word (so that "er" at the end of a word and "er" in the middle can become different tokens). Here is the corpus after Step 1:

l o w _
l o w e r _
l o w e s t _
n e w e r _
w i d e r _

Merge 1. Count adjacent pairs. Five pairs tie at 3 occurrences: l o, o w, w e, e r and r _; everything else occurs once. We need a tie-break; let's use "the pair seen first when reading the corpus left to right", which is l o. Merge it into a new symbol lo:

lo w _
lo w e r _
lo w e s t _
n e w e r _
w i d e r _

Merge 2. Recount. Now lo w occurs 3 times (it inherited the count of o w), tied with w e, e r, r _. First seen is lo w, so merge to low:

low _
low e r _
low e s t _
n e w e r _
w i d e r _

Merge 3. Recount. low e occurs 2 times, e r 3 times, r _ 3 times. The top count is 3, and e r comes first in reading order (it appears in "low e r _" before r _ does). Merge to er:

low _
low er _
low e s t _
n e w er _
w i d er _

Merge 4. Recount. er _ occurs 3 times and everything else at most 2. Merge to er_, a token that means "the suffix -er at the end of a word":

low _
low er_
low e s t _
n e w er_
w i d er_

After four merges the vocabulary is the original characters plus lo, low, er, er_, and the merge list is [(l,o), (lo,w), (e,r), (er,_)]. At this point every remaining pair occurs at most twice; on a five-word corpus further merges are decided by tie-breaks, which is why real tokenizers are trained on billions of words where the counts are meaningful. Even here, though, look at what emerged: a stem low and a suffix er_, from nothing but counting.

Now run the algorithm yourself on any corpus you like. The default is the classic example from the Sennrich paper, where the words have frequencies (newest six times, widest three) so the counts are less tie-heavy.

Encoding new text with learned merges

Training gives us a vocabulary and an ordered list of merges. To tokenize new text we do not recount anything. We split the text into base symbols and apply the merges in the order they were learned: for each merge rule, scan the word and replace every occurrence of that pair. The order matters because later merges were learned on top of earlier ones; lo w → low only makes sense once l o → lo has fired.

An equivalent and faster formulation, used by real implementations: give every merge a rank (its position in the list). To encode a word, repeatedly find the adjacent pair with the lowest rank present in the word and merge it, until no pair in the word has a rank. Try it on lowest with our four merges: l o w e s t _ → (rank 1) lo w e s t _ → (rank 2) low e s t _; e s and s t were never merged, so we stop with [low, e, s, t, _]. The unseen word slower becomes [s, low, er_], which is not bad for an algorithm that has never seen it.

from collections import Counter

def get_pairs(word):                       # word is a tuple of symbols
    return Counter(zip(word, word[1:]))

def train_bpe(corpus, num_merges):
    vocab = Counter(tuple(w) + ("_",) for w in corpus.split())   # word -> count
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for word, n in vocab.items():
            for pair, c in get_pairs(word).items():
                pairs[pair] += c * n
        if not pairs:
            break
        best = max(pairs, key=pairs.get)                           # most frequent pair
        merges.append(best)
        vocab = Counter({merge_word(w, best): n for w, n in vocab.items()})
    return merges

def merge_word(word, pair):
    out, i = [], 0
    while i < len(word):
        if i < len(word) - 1 and (word[i], word[i + 1]) == pair:
            out.append(word[i] + word[i + 1]); i += 2
        else:
            out.append(word[i]); i += 1
    return tuple(out)

def encode(word, merges):
    word = tuple(word) + ("_",)
    for pair in merges:                                            # apply in learned order
        word = merge_word(word, pair)
    return list(word)

merges = train_bpe("low lower lowest newer wider", 4)
print(merges)
print(encode("slower", merges))

The full version, with byte-level base symbols, rank-based encoding, decoding, and saving/loading, is in code/lumen/tokenizer.py. Python's max breaks ties by first insertion into the Counter, which matches the "first seen" rule we used by hand.

Byte-level BPE: GPT-2's trick

Sennrich's BPE worked on characters, which reintroduces the unknown-character problem for any symbol not in the training data. GPT-2 (Radford et al., 2019) made the base alphabet the 256 byte values instead, so that the tokenizer can never fail. Every merge is then between byte sequences, and the vocabulary of 50,257 is 256 bytes + 50,000 learned merges + one special token, <|endoftext|>.

There is one engineering wrinkle. Many byte values are control characters or whitespace that are awkward to store in a text file of vocabulary entries. GPT-2 therefore maps each of the 256 bytes to a printable Unicode character (the readable bytes map to themselves; the rest are shifted into a range of visible symbols). This is why, if you open GPT-2's vocabulary, you see entries like Ġthe: Ġ is the printable stand-in for the space byte, so Ġthe means " the" with its leading space. It is purely cosmetic; the model sees only integer ids.

The pre-tokenization regex and why it exists

Before any merging, GPT-2 splits the text with a regular expression. Here it is, in full:

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

Read the alternatives left to right. Common English contractions ('s, 't, 're…) become their own chunks. Then: an optional space followed by a run of letters; an optional space followed by a run of digits; an optional space followed by a run of anything that is neither whitespace, letter nor digit (punctuation); and finally runs of whitespace. BPE merges are then learned and applied within each chunk only.

Why bother? Without this, the most frequent pairs in English text would include things like e␣ and ␣t, and BPE would happily learn tokens that straddle word boundaries, such as world! or of␣the. Those are frequent but they explode the vocabulary with combinations and make the same word look different in every context. The regex enforces three sensible rules: the space attaches to the following word (so Ġworld is one token, and "world" at the start of a line is a different token), digits are separated from letters (so 2017 is not glued to whatever precedes it), and punctuation is its own chunk.

Later tokenizers refined the pattern. GPT-4's cl100k_base splits digits into groups of at most three, so that a long number is tokenized in a consistent way rather than by whatever byte pairs happened to be frequent, and adds case-insensitive contractions. Llama 3 adopted a similar pattern with a 128,256-entry vocabulary (Dubey et al., 2024). These are small choices with real downstream effects on arithmetic, which we return to below.

Below is a real, minimal byte-level BPE trained on a short English paragraph when the page loads (about sixty merges, so it is a toy compared with GPT-2's fifty thousand). Type anything and watch how it splits. Characters that never appeared in the training paragraph fall back to their UTF-8 bytes, exactly like the real thing.

WordPiece and SentencePiece / Unigram, in brief

BPE is the most common tokenizer family but not the only one. Two others show up constantly, and the differences are worth knowing because they change how the same text gets split.

WordPiece

WordPiece (Schuster & Nakajima, 2012; used by BERT) trains almost like BPE, but picks the pair to merge by a different score: instead of the raw count of the pair, it uses the count divided by the product of the counts of the two parts, roughly a measure of how much more often the pair appears than chance. This favours merging pieces that are strongly bound to each other over pieces that are merely common. At encoding time, WordPiece does not replay merges; it greedily takes the longest vocabulary entry that matches at the current position, and marks word-internal pieces with a ## prefix (unhappiness → un ##happi ##ness).

SentencePiece and the Unigram model

SentencePiece (Kudo & Richardson, 2018) is a library rather than an algorithm; its main idea is to treat the input as a raw stream of Unicode characters, with spaces turned into a visible ▁ symbol, so that no language-specific pre-tokenization is needed. It can train BPE, but its other algorithm, Unigram (Kudo, 2018), works backwards: start with a very large candidate vocabulary and repeatedly remove the pieces whose loss hurts the likelihood of the corpus least, under a model where each piece has an independent probability. At encoding time, Unigram picks the segmentation with the highest total probability using dynamic programming, and can sample alternative segmentations for regularisation. Llama 1 and 2 used SentencePiece BPE with a 32,000 vocabulary; T5 used Unigram.

How big should the vocabulary be?

The number of merges is a free choice, and it is a genuine trade-off. More merges means longer tokens, so fewer tokens per document (better compression, cheaper attention, longer effective context). But every vocabulary entry costs a row of $d_{model}$ parameters in the embedding table and another in the output layer, and the softmax over the vocabulary gets more expensive. Rare tokens also get fewer training examples each, so their embeddings are poorly learned; the very rarest become "glitch tokens" (below).

The trend has been upward: GPT-2 used 50,257, GPT-4's cl100k_base about 100,000, Llama 3 128,256, and some recent models exceed 250,000, partly to serve many languages well. Tao et al. (2024) argue that the optimal vocabulary grows with model size, which fits: in a 124M-parameter model the embedding table is a third of all parameters, in a 70B model it is well under 1%.

Special tokens

Some tokens are not learned from text at all. They are added by hand to mark structure the model needs to see, and they get their own embedding rows like any other token.

• End of sequence / end of text (<|endoftext|> in GPT-2, </s> in Llama 2, <|end_of_text|> in Llama 3). During pre-training it separates documents in the concatenated stream so the model learns that a new document can begin anywhere. During generation, sampling it means "stop".
• Beginning of sequence (<s>, <|begin_of_text|>). Gives the first real token something to attend to and marks "this is the start"; many models are noticeably worse if you forget it.
• Padding. When batching sequences of different lengths, shorter ones are filled with a pad token that is masked out of the loss and out of attention. It carries no meaning and is often just reused from another special token.
• Chat template tokens. Assistant models add markers for the roles in a conversation, such as Llama 3's <|start_header_id|>user<|end_header_id|> and <|eot_id|> (end of turn). The supervised fine-tuning chapter shows how they are used to teach a base model the shape of a dialogue.

Why tokenization causes weird behaviour

Because the model never sees letters, only token ids, a whole class of "the model is dumb" observations are really "the tokenizer hid the information". Here are the most common ones.

Counting the r's in "strawberry"

A famous failure: ask a model how many times the letter r appears in "strawberry" and it may say two. Look at what the model actually receives. Depending on the tokenizer, "strawberry" arrives as two or three tokens, something like str aw berry. There is no token for "r". To count letters, the model has to know the spelling of each token, which it can only have learned implicitly from seeing those tokens near their spelled-out forms in training data. It is like asking someone how many letters are in a word they have only ever heard, never read.

Arithmetic on digits

Under GPT-2's regex, a number like 20170601 is a run of digits that BPE merges by frequency, so it might split as 201 70 601 while 20170602 splits as 2017 06 02. Two numbers that differ in the last digit look completely different to the model, and column-wise addition (which needs aligned digits) is hopeless. This is why newer tokenizers force digits into fixed groups of one to three, and why some models trained specifically for maths tokenize every digit separately (Llama 1 and 2 did this). The tokenizer, not the model's intelligence, is a large part of whether an LLM can add.

Non-English inefficiency

BPE learns merges from its training corpus, which is mostly English for most tokenizers. Common English words become single tokens; the same meaning in a less-represented language may cost five or ten tokens, sometimes one per byte. Petrov et al. (2023) measured this across languages and found that the same text can require several times more tokens in some languages than in English, and up to roughly fifteen times more in the worst cases for some tokenizers. Since tokens cost money, latency and context space, users of those languages pay more for less. Larger, deliberately multilingual vocabularies (Llama 3's 128k, and the 250k-class vocabularies in some recent models) reduce but do not remove the gap.

Glitch tokens

If a string is common in the tokenizer's training data but rare in the model's training data, it gets a vocabulary entry whose embedding is almost never updated, and stays close to its random initialisation. Feeding such a token to the model produces bizarre behaviour: it may refuse to repeat it, replace it with something unrelated, or ramble. The best known example is SolidGoldMagikarp, a Reddit username that made it into GPT-2's vocabulary (Rumbelow & Watkins, 2023). Land & Bartolo (2024) show how to detect such under-trained tokens systematically. The lesson: a tokenizer trained on different data from the model leaves landmines.

Whitespace, capitalisation, and prompt sensitivity

Because the space attaches to the following word, Ġhello, hello, ĠHello and Hello are four different tokens with four different embeddings. A prompt that ends with a trailing space forces the next token to be one without a leading space, which is rare in the training data, and quality drops. Code models feel this acutely: indentation is whitespace, and GPT-2's tokenizer encoded each space of a Python indent as its own token until later tokenizers added multi-space tokens.

Fertility and what tokens cost

The number of tokens per word for a tokenizer on a given text is called its fertility. For English with a modern tokenizer it is around 1.3; a rule of thumb is 100 tokens for roughly 75 words. Fertility matters for three concrete reasons.

Money. API providers price per token, so the same request costs more in a high-fertility language, and a verbose tokenizer inflates every bill. Context. A model with a 128k-token window fits about 100k English words but far fewer Burmese words. Compute. Attention scales with the square of sequence length, so halving fertility roughly quarters attention cost for the same content, and training on a fixed number of tokens covers more text.

There is a subtler cost too. Each token is one "step" of computation for the model. A concept spread across five tokens gets five forward passes of processing; one crammed into a single token gets one. This is one reason models can reason better about common English words than about rare technical terms with the same meaning: the representation is spread differently.

Practice

The companion file code/lumen/tokenizer.py contains a byte-level BPE with train, encode, decode and save/load. The exercises build on it.

Further reading

• Sennrich, Haddow & Birch (2016). Neural Machine Translation of Rare Words with Subword Units. The paper that brought BPE to NLP; the worked example in section 3 is the one our interactive defaults to.
• Radford et al. (2019). Language Models are Unsupervised Multitask Learners. Section 2.2 describes byte-level BPE and the reasoning behind it.
• Kudo & Richardson (2018). SentencePiece, and Kudo (2018). Subword Regularization. The library and the Unigram model.
• Wu et al. (2016). Google's Neural Machine Translation System. The WordPiece description most people cite.
• Petrov et al. (2023). Language Model Tokenizers Introduce Unfairness Between Languages. Measurements of cross-language fertility.
• Land & Bartolo (2024). Fishing for Magikarp. Automatically finding glitch tokens.
• Tao et al. (2024). Scaling Laws with Vocabulary. Evidence that larger models want larger vocabularies.
• OpenAI. tiktoken. A fast BPE implementation with the GPT-2, GPT-4 and later vocabularies; useful for checking your own against the real thing.