Vol. II · Tokens Plate 4 of 10encoding, pre-tokenisation, regular expression, merge order, word boundariesAD

Encoding With BPE.

Split the text into words, then replay the merges inside each word, lowest-ranked first, until no merge applies.

A trained BPE tokeniser is a list of merges in order. To encode a new text, it first cuts the text into pre-tokens with a regular expression — roughly, words with their leading space, runs of digits, runs of punctuation, and runs of whitespace. Then, inside each pre-token, it starts from bytes and repeatedly applies whichever merge that is present has the lowest rank (was learned earliest), until none applies. Different words never interact, so encoding is fast and can be cached word by word.

The pre-tokenising regex is the least visible and most consequential part of a tokeniser. Without it, merges cross word boundaries: BPE happily learns tokens such as of the or in the , which make the vocabulary depend on which words happen to be adjacent. With it, every token sits inside one word, a space attaches to the start of the word that follows, and the same word is always tokenised the same way wherever it appears.

Below: left, a word encoded by the course tokeniser one merge at a time. Right, the text cut into pre-tokens, then encoded by two BPE tokenisers trained in your browser on the same text — one that split into words first and one that did not.

What you will learn

Apply a merge list to a new word, merge by merge.
Explain what pre-tokenisation does and why tokenisers use it.
Compare tokenisers trained with and without word boundaries.
Read the GPT-2 pre-tokenisation pattern.

Workshop

Left: the word in the course tokeniser, one line per merge applied (lowest rank first). Right: the text’s pre-tokens, and its tokens under 300-merge BPE tokenisers trained with and without pre-tokenisation.

Words first, then merges

The course tokeniser turns ·unbelievably into its final tokens in 7 merges, each one the lowest-ranked merge available at that moment; the order is the order in which the merges were learned, not left to right. The sample text has 9 pre-tokens. A 300-merge BPE trained on the same 60 000 characters with word boundaries encodes it in 16 tokens; one trained without them needs only 14, because 115 of its 300 merges span a space — of the and in the become single tokens. That looks like a gain, but it is a bad trade: the vocabulary is spent on accidents of adjacency, the same word is tokenised differently depending on its neighbour, and the model must learn the meaning of the separately inside dozens of fused tokens.

The GPT-2 pattern shown above has become a template. It keeps contractions such as ’s apart, attaches one leading space to a word, keeps runs of letters, of digits and of other symbols separate, and leaves trailing whitespace on its own. Later tokenisers changed details that turned out to matter — for example cutting long runs of digits into groups of at most three, which makes numbers tokenise consistently (plate II.8) — and some, such as SentencePiece models, skip regex splitting and mark spaces with a special character instead. The course tokeniser uses the GPT-2 pattern exactly, which is why its tokens never contain a space after their first character.

Because encoding works word by word, a tokeniser can memoise each word’s tokens; production tokenisers such as OpenAI’s tiktoken encode hundreds of megabytes of text a second this way, in Rust.

Terms

Pre-tokenisation: Splitting text into word-like pieces with a regular expression before applying merges.
Merge rank: The position of a merge in the learned list; lower ranks are applied first.
Encoding: Turning a text into token ids with a trained tokeniser.
Decoding: Turning token ids back into text by concatenating their bytes.

Encoding is pre-tokenise, then replay merges by rank inside each word. Word boundaries keep the vocabulary about words, not about which words happen to be neighbours.