Tokens

Our model’s window holds eight characters. If the text ends in “the litt”, it contains the short word “the”, but the next word does not fit in full. We could enlarge the window, but that would also enlarge the network’s first layer. Let’s try another approach: make each position hold a bigger piece of text.

Many language models do this with variable-length tokens. A common word may fit in one token; a rare word may need several. The pieces need not follow syllable or morpheme boundaries: a tokenization algorithm chooses them. Sprout has a vocabulary of 8,192 tokens. Let’s see how it handles familiar words and unfamiliar Russian text.

How Sprout reads

Below is Sprout's real tokenizer, the very one it was trained with. Each colour is a separate token. Type anything, or try the ready-made examples, Russian text and emoji included.

A few things jump out straight away.

• Common words are a single token, including the space in front of them: "·time", "·little", "·garden". To the model, "·the" in mid-sentence and "The" at the start are different tokens.
• A rare word is built from pieces. antidisestablishmentarianism turns into nine tokens: "·ant | id | is | est | ab | lish | ment | arian | ism". The vocabulary has no single token for this word, so the tokenizer uses its parts.
• Numbers go one digit at a time. That's not an accident but a rule; more on it below.
• Russian text falls apart: nearly every letter becomes two token shards. The sample "Жили-были дед да баба…" has 22 characters and 41 tokens. The 🌱 sign splits into four byte tokens.

The bottom of the widget shows what we gained. A window of eight letters is a scrap of a word. A window of eight tokens of English is almost a whole phrase: on our validation text a token averages 4.085 characters, so eight slots hold about 33 characters. In Russian, though, the window gets even smaller than the letter one: eight tokens are just four or five letters. Why that happens is the plot twist of this chapter.

Letters are too small, words too big

Before inventing tokens, let's look at the two obvious options.

Letters. The vocabulary is tiny, 97 symbols for our cleaned texts; characters outside that set are not covered. But text gets long: a thousand-character story is a thousand steps, each a tiny decision about the next letter. Everything the model needs to remember is stretched over a huge number of positions. In chapter 7 we'll see that the number of position pairs in full attention grows quadratically with sequence length: four times as many positions means sixteen times as many pairs. That describes this part of the calculation, not the entire model’s running time.

Words. The text is short, each slot a whole word. But the vocabulary swells. In our validation text alone, 7.2 million tokens of simple stories and conversations, we counted 28,666 different words, and 6,357 of them appear exactly once. Every word needs its own row in the embedding table, and rare rows barely learn anything. Worse, any new word (a name, a typo, "Sprout" in some other spelling) falls outside the vocabulary, and all the model gets is an "unknown" tag.

Pieces of words are the happy medium. Common words stay whole, rare ones are built from parts, and something completely unfamiliar can be spelled out letter by letter. There are no unknown words at all. On our validation text, a word with a space in front of it is exactly one token 95% of the time: almost as good as a word vocabulary, without its problems.

Bytes at the very bottom

Where should the cutting start? With letters, you'd think, but the world's scripts have tens of thousands of characters, Chinese ones included, and then there are arrows and emoji. Sprout's tokenizer, like GPT-2's and many modern models', starts from bytes.

Sprout converts text to UTF-8. In this encoding, a Unicode code point uses one to four bytes, and a byte holds a number from 0 to 255. Plain Latin letters, digits and ASCII punctuation use one byte; Russian letters use two. Their first byte, D0 or D1, carries part of the code point’s number and the second carries the rest: there is no separate “Cyrillic ahead” instruction. The 🌱 sign takes four bytes. But a visible symbol can contain several code points, as with a skin-tone emoji or a family group, and then it uses more bytes.

for s in ['a', 'ж', 'é', '🌱', 'Росток']: b = s.encode('utf-8') print(f'{s!r:10} {len(s)} chars -> {len(b):2} bytes:', ' '.join(f'{x:02X}' for x in b))

Sprout’s first 256 tokens cover every possible byte value. It can therefore encode valid Unicode text even without familiar words, falling back to one byte at a time. Another 7,932 tokens come from successive merges, and four identifiers are reserved for special markers: $256 + 7\,932 + 4 = 8\,192$ in total.

Glue the most frequent pair

The algorithm is called BPE, byte pair encoding. It is strikingly simple:

1. Write the whole training text as bytes.
2. Count which pair of neighbouring tokens occurs most often.
3. Declare that pair a new token and replace every occurrence of it.
4. Repeat until the vocabulary is as big as you want.

Try it yourself on a tiny text. Every press is one merge.

The pairs with the most occurrences go first: "a"+"t", "t"+"h", then "th"+"e", and "the" is already a single token. Then a space sticks to it. Words that repeat a lot quickly become whole tokens; rare ones stay in pieces. No linguistics at all, just counting.

Here's the same algorithm in plain Python, in a couple of dozen lines. Run it and compare the merges with the widget: they match.

import re from collections import Counter text = "the cat sat on the mat. the cat ate the rat. then the rat ran to the hat." # pre-split like tokenizer.py (an ASCII-only version): words keep their leading space chunks = Counter(re.findall(r" ?[A-Za-z]+| ?[0-9]| ?[^\sA-Za-z0-9]+|\s+", text)) seqs = {w: list(w.encode()) for w in chunks} vocab = {i: bytes([i]) for i in range(256)} print(sum(len(s) * chunks[w] for w, s in seqs.items()), 'tokens to start with') for step in range(10): pairs = Counter() for w, seq in seqs.items(): for pair in zip(seq, seq[1:]): pairs[pair] += chunks[w] if not pairs: break best = max(pairs, key=pairs.get) new = 256 + step vocab[new] = vocab[best[0]] + vocab[best[1]] for w, seq in seqs.items(): out, i = [], 0 while i < len(seq): if i + 1 < len(seq) and (seq[i], seq[i + 1]) == best: out.append(new) i += 2 else: out.append(seq[i]) i += 1 seqs[w] = out left = sum(len(s) * chunks[w] for w, s in seqs.items()) print(f'merge {step}: {vocab[best[0]]!r} + {vocab[best[1]]!r} -> {vocab[new]!r} seen {pairs[best]}x, {left} tokens left')

First, cut into chunks

One subtlety. If pairs were merged across the whole text, BPE would happily learn tokens like "g." or "d the": such combinations are common too. But they mix the end of one word with the start of the next, and vocabulary slots get wasted. So before training, the text is cut into chunks with a regular expression, and merges never cross a chunk's borders. Switch the widget at the top of the chapter to "Chunks" to see those borders.

Here is the regular expression, straight from tokenizer.py:

# Split text into chunks first, so a merge never crosses a word boundary: # contractions, words with their leading space, single digits, punctuation, spaces. SPLIT = re.compile(r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

Let's take it apart at the vertical bars, which mean "or":

• '(?:[sdmt]|ll|ve|re) — English contractions: 's, 't, 'll, 've, 're. "didn't" is cut into "didn" and "'t".
• ?\p{L}+ — a word made of letters of any alphabet, together with one space before it. That's where "·little" comes from.
• ?\p{N} — a single digit. So 2024 is four tokens. That makes place value easier for the model to see and keeps numbers from turning into thousands of arbitrary tokens.
• ?[^\s\p{L}\p{N}]+ — a run of punctuation, like '!"' or "...".
• \s+(?!\S)|\s+ — spaces and newlines.

And here is the training loop itself. It does exactly what our mini BPE does, but counts more cleverly: it remembers which chunks contain each pair, and after a merge it recounts only those. Without that, 7,932 merges over 120 thousand documents would take hours; with it, Sprout's tokenizer trained in 19 seconds.

@classmethod def train(cls, texts, vocab_size, specials=SPECIALS, verbose=False): n_merges = vocab_size - 256 - len(specials) words = Counter() for text in texts: for chunk in SPLIT.findall(text): words[chunk] += 1 # every distinct chunk is a list of token ids, counted once with its frequency seqs = [list(w.encode()) for w in words] freqs = list(words.values()) pairs = Counter() where = defaultdict(set) # pair -> indices of chunks that contain it for i, seq in enumerate(seqs): for pair in zip(seq, seq[1:]): pairs[pair] += freqs[i] where[pair].add(i) merges = [] for step in range(n_merges): if not pairs: break best = max(pairs, key=pairs.get) new_id = 256 + step merges.append(best) for i in list(where[best]): seq, f = seqs[i], freqs[i] for pair in zip(seq, seq[1:]): # forget this chunk's old pairs pairs[pair] -= f if pairs[pair] <= 0: del pairs[pair] where[pair].discard(i) seq = merge(seq, best, new_id) seqs[i] = seq for pair in zip(seq, seq[1:]): # and count the new ones pairs[pair] += f where[pair].add(i) if verbose and step % 500 == 0: tok = cls(merges).vocab[new_id] print(f'merge {step:5d}: {tok!r}') return cls(merges, specials)

The output is real, from Sprout's training (the log counts merges from zero): the very first merge is "·t", by step 500 the tokenizer is already gluing whole words like "·flow", and step 7,000 gives "·ambulance".

How a word is put together

Now we have a vocabulary. How do we cut up new text? Encoding simply replays the merges in the order they were learned: while the chunk contains a pair from the vocabulary, merge the one that was learned earliest.

def encode_chunk(self, chunk): ids = self.cache.get(chunk) if ids is not None: return ids ids = list(chunk.encode()) while len(ids) > 1: # the pair that was learned earliest gets merged first pair = min(zip(ids, ids[1:]), key=lambda p: self.merges.get(p, float('inf'))) if pair not in self.merges: break ids = merge(ids, pair, self.merges[pair]) if len(self.cache) < 500_000: self.cache[chunk] = ids return ids

The result is easiest to draw as a tree: bytes at the bottom, merges above them, the finished token on top. Each merge's number is its place in the training queue.

Look at "·the": merge no. 1 is "·t", no. 2 "he", and by the seventh merge the whole "·the" is learned. Long words take ages, counted in merges: "·butterfly" waited until no. 2,095, and "·Congratulations" (16 bytes, one of the two longest tokens in the vocabulary; the other is "·recommendations") only appeared at no. 4,312. Curiously, lower-case "·sprout" is one token while capitalised "·Sprout" is three: the capitalised form was rarer in the stories. And "·Росток" is thirteen bytes (the space plus two per letter) with not a single merge.

What's in the vocabulary

Let's walk through the vocabulary from the first merge to the last. Move the slider: at the start come letter pairs and short common words, further on longer and rarer words and names.

The first merges are "·t", "he", "·a", "·s", "·w", "in", and the seventh is "·the". At the very end come "·mushrooms", "Josh", "·armcha" (half an armchair: the whole word never made it), "·recommendations". More than half the vocabulary consists of a space followed by letters: whole words or their beginnings.

The final four identifiers, 8188–8191, are special tokens: <|endoftext|>, <|user|>, <|assistant|> and <|end|>. BPE does not learn them through ordinary merges. The program either inserts their identifiers explicitly or lets the tokenizer recognise their written forms. During ordinary corpus preparation, that recognition is disabled with allow_special=False. It is enabled in this demonstration: the “specials” example displays each marker as one chip. The first separates stories; the others mark chat roles and the end of a turn.

How many tokens do we need?

Why 8,192 and not 1,000 or 100,000? A bigger vocabulary means shorter text but a more expensive model. The slider below shows what a smaller vocabulary would do. Nothing has to be retrained: BPE learns greedily, one merge at a time, so stopping training earlier would have given us exactly the first merges of our vocabulary.

Vocabulary	Characters per token	Embedding table ×384
256 (bytes only)	1.00	98,304
512	2.21	196,608
1,024	2.91	393,216
2,048	3.50	786,432
4,096	3.88	1,572,864
8,192	4.09	3,145,728

The first 256 merges more than halve the length of the text. Every further doubling of the vocabulary buys less: going from 4,096 to 8,192 tokens saves only 5% of the length while the embedding table doubles. In Sprout it already weighs 3.15 million parameters, almost a fifth of the model.

There is a second price too. The bigger the vocabulary, the rarer each token and the worse its embedding learns. Even with 8,192 tokens, 137 of the learned merges never once appear in the 7.2 million tokens of validation text, and 506 appear fewer than ten times. For a 17-million-parameter model writing simple English stories, 8,192 is a sensible compromise.

Comparing models with different tokens

Since the length of a text depends on the vocabulary, there's a trap here. The model at the end of this chapter is the same kind of network as last time, the same MLP class from snapshots.py in a new size, MLP(8192, 8, 48, [384]): eight tokens of 48 numbers and one hidden layer of 384 neurons. On validation text its surprise is 3.31 nats per token. The letter model had 1.103 nats per letter. Three times worse?

No: we're comparing different things. Guessing the next token means guessing about four characters at once, and the surprise for all of them adds up. The fair comparison is per unit of text. If a token holds $c$ characters on average, then

$$\text{nats per character} = \frac{\text{nats per token}}{c} = \frac{3.31}{4.085} \approx 0.81.$$

That's clearly better than the letter model's 1.103. Researchers watch out for the same trap: the perplexities of models with different tokenizers can't be compared directly, so they are first converted to a per-character or per-byte figure.

Zipf's law

Tokens occur very unevenly. The linguist George Zipf noticed this for words back in the 1930s and 40s: the second most frequent word occurs about half as often as the first, the third a third as often, and so on. Frequency is inversely proportional to rank. Draw it with both axes on a log scale and you get an almost straight line.

Tokens come out nearly Zipfian: our curve's slope in the middle is about −1.2 against the ideal −1. In practice this means a small handful of tokens does most of the work. The most common token, the full stop, is 7.2% of the text. The top ten tokens cover 27.9% of it, the top hundred 56.2%, the top thousand 86.1%. The other seven thousand share less than a seventh of the text between them. That's why a huge vocabulary pays off poorly: each new merge is a rarer word.

An honest word about Russian

Now it's clear why Russian text falls apart into shards. Sprout's tokenizer learned only from English stories. There was practically no Cyrillic in the corpus, since cleaning removed non-English texts, and not one of the 7,932 merges contains a byte above 127. So for Russian the tokenizer has nothing but the 256 byte tokens: every letter costs two tokens, and every space one more.

• "Once upon a time there lived an old man and an old woman. They had a hen." — 73 characters, 20 tokens: 3.65 characters per token.
• «Жили-были старик со старухой. Была у них курочка.» (the same opening in Russian) — 49 characters, 88 tokens: 0.56 characters per token.
• «Росток» ("Sprout" in Russian) — 6 letters, 12 tokens.
• 🌱 — one character, 4 tokens.

To Sprout, the same story in Russian is more than four times as long. Its context is 512 tokens: about 2,100 characters of English but under 300 characters of Russian, a couple of paragraphs against a couple of sentences. And that's not all. In 7.2 million tokens of validation text, bytes above 127 turned up only 30 times. Their embeddings have barely been trained: to Sprout, a Russian letter is two almost meaningless vectors in a row.

Tokenization efficiency depends on the tokenizer’s training data, vocabulary and design. A multilingual BPE tokenizer can learn Cyrillic merges and make Russian sequences much shorter. That is separate from training the language model: encoding a sentence compactly does not imply being able to answer it. The relative token costs of languages need to be measured for the particular tokenizer.

Why does Sprout spend six tokens on the Russian word «кот» ("cat") but one on the English " cat"?

Russian words are longer than English ones The tokenizer deliberately blocks Russian text Each Russian letter is two bytes, and the vocabulary has no merges for Cyrillic: the corpus was English

BPE learned only the pairs that were frequent in the training text. There was almost no Cyrillic there, so Russian letters stay as pairs of bytes, while " cat" was merged into a single token early in training.

What if the text contains something really strange?

Byte-level BPE can encode any valid Unicode text because its vocabulary includes every original byte. For example, “猫” uses three bytes, 🌱 uses four, and the family emoji 👨‍👩‍👧‍👦 uses 25. Sprout splits these examples into individual byte tokens. Its tokenizer can reconstruct the original text, but that says nothing about the model’s understanding. The reverse guarantee does not hold for generation: a model can choose bytes that fail to form a valid UTF-8 sequence.

Sprout right now

Sprout's build has barely changed: an eight-slot window, embeddings, a hidden layer. But every slot now holds a token, and the window spans about 33 characters instead of eight. Its surprise is 3.31 nats per token on validation text, or about 0.81 nats per character against 1.103 for the letter model. It has more parameters, too: of its 3.7 million, about 3.15 million sit in the output layer that scores every one of the 8,192 tokens. The prose hangs together better, but eight tokens are still just one phrase. How to look further back without bloating the network is the next chapter's subject: attention.