Roadmap / Theory

Tokenization

Train a byte-pair encoding tokenizer, then encode and decode with it.

A language model does not read text: it reads integers. The tokenizer cuts the text into pieces, the tokens, and gives each piece an integer id. That choice sets the vocabulary size, how long every sequence is, and which strings the model can represent at all. Almost every modern LLM (large language model) uses some form of BPE (byte-pair encoding), which this page builds from scratch, one step at a time.

Characters, words, or something in between

There are three natural ways to cut a text into pieces:

  • Words give short sequences, but the vocabulary has no limit: every new name, typo or inflection ("tokenizers", "tokenizing", "tokenisation") is a word the model has never seen, an unknown token.
  • Characters never produce unknown tokens, but sequences become several times longer, and the cost of attention grows with the square of the length (section 7).
  • Subwords sit in between: frequent words are single tokens, rare words are split into frequent pieces. "tokenization" might become "token" + "ization", and a word never seen before still breaks down into known parts.

Example. "the cat sat on the mat" is 6 words, but 22 characters (spaces included). As words, the model reads 6 tokens; as characters, 22: almost four times as many.

BPE learns the subword pieces from data: the pieces that occur often become tokens.

Bytes as the base alphabet

Before anything is merged, text must become a sequence of basic symbols. Unicode, the standard list of all characters, has well over 100,000 of them: too many for a base vocabulary. UTF-8 (Unicode Transformation Format, 8-bit; standardized in the RFC (Request for Comments) document 3629) writes every character as 1 to 4 bytes, numbers from 0 to 255. ASCII (American Standard Code for Information Interchange) letters take one byte, "รจ" takes two, most emoji take four.

Example. "a" is the single byte 97. "รจ" is the two bytes 195, 168. The emoji ๐Ÿ˜€ is the four bytes 240, 159, 152, 128.

Starting from the 256 possible byte values means that any string at all can be represented, in any language, and nothing is ever unknown. This is the "byte-level" BPE introduced with GPT-2 (Generative Pre-trained Transformer 2; Radford et al., 2019).

The price: one character can span several tokens, and a sequence of tokens does not always decode to valid UTF-8. Cut an emoji in half and you get bytes that are not a character: the first two bytes of ๐Ÿ˜€, 240 and 159, mean nothing on their own. Decoders therefore use errors="replace", which turns invalid bytes into the replacement character "๏ฟฝ".

Byte-pair encoding: training

BPE started as a data-compression algorithm (Gage, 1994), and was adapted to split words into subwords for machine translation by Sennrich, Haddow and Birch (2016). Training is a loop:

  1. Start from the training text as a list of byte values, ids 0 to 255.
  2. Count every pair of neighbouring ids.
  3. Take the most frequent pair, give it the next unused id (256, 257, ...), and replace every occurrence of the pair in the list with that id, left to right.
  4. Record the merge, and repeat until the vocabulary has the size you want.

Example. Train on the text aaabdaaabac (11 bytes) for three merges. Letters stand for their bytes: "a" is 97, "b" is 98.

merge pair (count) new id text after the merge
1 a a (4) 256 [256] a b d [256] a b a c
2 [256] a (2) 257 [257] b d [257] b a c
3 [257] b (2) 258 [258] d [258] a c

The new ids stand for aa, aaa and aaab, and the text shrinks from 11 tokens to 9, 7 and 5. In merge 2 the pairs [256] a and a b are tied at 2; the one seen first in the text, [256] a, wins. After three merges the text is 5 tokens instead of 11, and the vocabulary has 256+3=259256 + 3 = 259 ids.

The result of training is an ordered list of merges: (97, 97) โ†’ 256, (256, 97) โ†’ 257, (257, 98) โ†’ 258.

Two details decide whether two implementations agree:

  • Overlaps. In a a a, the pair (a, a) occurs at positions 0 and 1, but only one replacement fits: each byte can belong to one new token only. Scanning left to right and skipping past each replacement gives [256] a.
  • Ties. When two pairs have the same count, some rule must pick one. minbpe takes the pair that was counted first, that is, the one whose first occurrence comes earliest in the text, as in merge 2 above.

Encoding and decoding

Encoding a new text replays the merges: start from its bytes, and repeatedly apply the merge that was learned earliest among the pairs present, until no learned pair is left. The order matters: it must be the order of training, not the frequency of pairs in the new text, so that the same text is always cut the same way.

Example. Encode abaaab with the three merges above.

  1. Bytes: a b a a a b. The pairs present are a b, b a, a a; only a a (256) was learned. Merge it: a b [256] a b.
  2. Now [256] a (257) is present: a b [257] b.
  3. Now [257] b (258): a b [258].
  4. The pairs left, a b and b [258], were never learned: stop. The result is [97, 98, 258], 3 tokens.

Decoding is a lookup. Every id maps to a byte string: the 256 base ids are single bytes, and each merge glues together the byte strings of its two parts (256 is aa, 257 is aa + a = aaa, 258 is aaa + b = aaab). Join the byte strings of all the ids and decode the result as UTF-8.

Example. [97, 98, 258] is a + b + aaab = abaaab, the original text.

Pre-tokenization and special tokens

Run on raw bytes, BPE learns tokens such as "dog.", "dog!" and "dog?" separately, wasting vocabulary on the same word with different punctuation. GPT-2 therefore prevents merges across character categories (letters, digits, punctuation), with an exception for spaces. The text is first split with a regular expression into chunks such as " dog" and "!", and BPE runs inside each chunk. That is why GPT-2 tokens usually start with a space.

Special tokens such as <|endoftext|> are never produced by merges. They are added to the vocabulary separately and inserted between documents, so the model learns where one text ends and the next begins.

Other tokenizers differ in the details. SentencePiece (Kudo and Richardson, 2018) trains directly on raw sentences, without language-specific pre-tokenization, and supports both BPE and a unigram language model. tiktoken is OpenAI's fast BPE implementation for its models. The core loop is the one above.

References

Practice

0/3