Tokens

The model from the last chapter sees the last eight letters. Eight letters are just "the litt": not even a whole word fits, let alone a sentence. What if each of the eight slots held something bigger than a letter, like a whole common word, or at least a syllable?

That is exactly what every large language model does. Text is cut into tokens, pieces of different lengths, and each piece gets its own number and its own embedding. Sprout has 8,192 of them. Before we get to where they came from, let's look at how it cuts text up.

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 model has never seen the whole word, but it knows the 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 49 characters and 86 tokens. Each emoji is four shards.

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, and there is no such thing as an unknown letter. 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 cost of attention grows with the square of the text length: a text four times longer costs sixteen times as much.

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.

Computers usually store text in the UTF-8 encoding: every character takes one to four bytes, and a byte is a number from 0 to 255. Plain Latin letters, digits and punctuation take one byte. Russian letters take two: the first (usually D0 or D1 in hexadecimal) says "Cyrillic ahead", the second picks the letter. Emoji take four.

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))

There are 256 possible bytes, and they are the first 256 tokens of Sprout's vocabulary. So the tokenizer can write down any text in any language one way or another: at worst, byte by byte. Apart from four special tokens (more on them later), the other 7,932 are glued-together pairs learned from the corpus. How they were chosen comes next.

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 last four numbers, 8188–8191, belong to the special tokens: <|endoftext|>, <|user|>, <|assistant|> and <|end|>. Ordinary text never produces them; the program inserts them. The first separates one story from the next; the others come into play in chapter 12, when we teach Sprout to talk. Try the "specials" example in the widget at the top of the chapter: each marker is a single token, drawn as a solid chip.

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.

This holds for every model: a language that is scarce in the training corpus is expensive in the tokenizer too. The tokenizers of big multilingual models are trained on text in many languages at once, so they do have merges for Cyrillic. But the "token tax" on languages less common than English in the corpus never disappears; it only gets smaller.

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?

Nothing bad happens: any text is bytes, and all 256 bytes are in the vocabulary. A Chinese character becomes three byte tokens, a rare emoji four, and a composite emoji like "family of four" twenty-five. The model may not understand it, but it can always write it down and read it back without loss. That's why byte-level BPE never has an "unknown token".

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.