Tokenization Schemes

A tokenization scheme decides what one token is. The choice sets the vocabulary size and the sequence length, and those two are inversely related.

4 Common Schemes

For example, the word unbelievable.

1. Character level

• one token per character, so u, n, b, e, l, ... which is 12 tokens
• the vocabulary is tiny, about 100 symbols, since that is all the characters there are
• every sequence becomes very long since many tokens per sentence

2. Word level

• one token per word, so unbelievable is 1 token
• the vocabulary is huge, maybe 50,000 entries, and it is still never enough
• this is the open vocabulary problem, because a word you did not see in training, like unbelievableness, has no token and becomes <UNK>

3. Subword level

• one token per common piece, so un + believ + able, which is 3 tokens
• the vocabulary is medium, maybe 32,000 pieces
• a word never seen before can still be spelled out of pieces, so nothing becomes <UNK>
• this is what byte pair encoding builds, and it is what GPT uses

4. Byte level

• one token per byte of the UTF-8 encoding
• the vocabulary is exactly 256, and it covers every language and emoji, so it is universal
• sequences get even longer than character level for non-English text

Trade Off

• a smaller vocabulary gives longer sequences and a smaller embedding table
• longer sequences also raise attention cost, because attention grows with the square of the sequence length
• a larger vocabulary gives shorter sequences and a larger embedding table

The practical code side of splitting text is in Tokenization.

A word the scheme cannot cover is replaced by a placeholder, and those placeholders are described in Special Tokens.