Tokens

Step 1 of 7. In: the text "the cat climbed the". Out: five integers, [0, 2, 4, 5, 1]. ← Overview · next step: Embeddings →

A neural network computes with numbers, so before anything else the text has to become numbers. The unit it is cut into is the token: a piece of text taken from a fixed list, the vocabulary, in which every piece has an integer, its id. A token can be a whole word (cat), part of a word (ed), one character or even one byte. The model never sees letters, only the sequence of ids, and everything it predicts is an id too.

Why not words? Why not characters?

The two obvious choices both fail:

• Words. "climb", "climbs", "climbed" and "climbing" would be four unrelated entries, and so would every name, typo, number and word of every language: the list never ends. Worse, a word that was not in the list when the model was trained has no id at all.
• Characters (or bytes). Nothing is ever unknown: 256 bytes write any text. But "the cat climbed the" becomes 19 symbols instead of 4 words, attention costs grow with the square of the length (step 3), and each position carries almost no meaning on its own.

Subwords sit in between: frequent words stay whole, rarer words are written with a few frequent pieces, and anything left over falls back to single bytes, so nothing is ever unknown. GPT-2 writes "the cat climbed the" with 4 tokens: the, cat, climbed, the.

Bytes first

Text is stored as bytes, in UTF-8: one byte for each ASCII character, two to four for the others — "a" is the byte 97, "ã" is two bytes, 195 and 163. A byte-level tokenizer such as GPT-2's starts from the 256 possible bytes, so any string at all, in any language, can be encoded. Our toy starts from the characters of a small corpus instead (23 of them), which keeps its tables short; the algorithm is the same.

BPE: merge the most frequent pair, again and again

The vocabulary is learned from a corpus by byte-pair encoding (BPE)¹, before the model is trained and separately from it:

1. Cut the corpus into words, and each word into characters (bytes, in GPT-2).
2. Count every pair of neighbouring symbols. Merge the most frequent pair into a new symbol, and write that merge down.
3. Repeat until the vocabulary has the size you want.

To tokenize new text, apply the recorded merges in the same order. GPT-2 learned 50,000 merges from English web text². Our toy tokenizer learns from eight sentences:

the cat sat on the roof. · the dog sat on the floor. · the cat jumped on the wall. · the dog jumped on the sofa. · the cat likes to climb the wall. · the dog climbs on the sofa. · the cat walked to the roof. · the dog walked to the floor.

Like GPT-2, it first cuts before each space and each punctuation mark, and the space stays at the start of the next word (written ␣ below). Then it counts. The most frequent pair of the corpus is t + h, 16 times (every "the"), so merge 1 is th; then th + e (16), then ␣ + the (8), ␣ + c (6)… After 40 merges every piece the toy model needs exists, and the tokenizer's vocabulary has 23 characters + 40 merges = 63 entries.

The running sentence is not in the corpus. Tokenizing it means starting from its 19 characters and applying the 40 merges in order; only 11 of them find a pair to merge:

"climbed" never appears in the corpus, and BPE writes it anyway, with two pieces it learned elsewhere: ␣climb (from "climb" and "climbs") and ed (from "jumped" and "walked"). Merges that do not touch the sentence — ␣on, ␣sofa, ␣jumped… — are about words it does not contain. GPT-2, with 50,000 merges learned from far more text, has a single token for climbed (id 19952).

The space belongs to the next word

"the" at the start of the text and " the" after a space are two different tokens: ids 0 and 1 in the toy, 1169 and 262 in GPT-2 ("The", capitalized, is a third one, 464). Neither the tokenizer nor the model knows they are "the same word". That is also why a prompt that ends in a space changes what the model predicts: the space would normally be the start of the next token (the LLMs chapter measures it).

Vocabulary and ids

The toy model keeps 12 tokens: 11 of the 63 pieces (the five of the sentence and six others it can predict) and the special token <|endoftext|> (below).

"the cat climbed the" → the ␣cat ␣climb ed ␣the → [0, 2, 4, 5, 1]

A real model has one row for every entry of its tokenizer: GPT-2's vocabulary is 256 bytes + 50,000 merges + 1 special token = 50,257, and it reads the sentence as [1169, 3797, 19952, 262]. The toy keeps 12 so that its tables fit on a page.

The ids are names, not quantities: 4 is not "twice" 2, and nothing in the number says "verb". The next step turns each id into a vector.

Special tokens

Some entries do not come from BPE. They are added by hand, and ordinary text never produces them:

• <|endoftext|> (GPT-2's id 50256, our 11) separates documents in the training data and lets the model end its own text: when generation draws it, it stops (step 7).
• Chat models add markers for whose turn it is; BERT uses [CLS], [SEP] and [MASK]. A batch of sentences of different lengths is filled with a padding token, which a mask then hides (step 4).

Portuguese costs more

A tokenizer is fitted to its corpus, so a language it saw little of is written with smaller pieces. GPT-2 was fitted on English:

The two toy tokenizers of these pages show the same effect from the other side: the English one cuts "o gato subiu no telhado." into 21 pieces, while the Portuguese one, fitted on Portuguese sentences, keeps gato whole — which GPT-2 does not. More tokens means more compute (attention grows with \(n^2\)), less text in the same context window and a bigger bill for the same sentence³.

See it run

The simulator runs the toy tokenizer, merge by merge, on any text you type. Try the cases: the sentence with its answer, a word the corpus never saw ("bird", written letter by letter) and the Portuguese sentence through the English tokenizer.

← Overview · next step: Embeddings →