The Mechanics of Tokenization: Byte-Pair Encoding and Beyond

Tokenization is the foundational step in any Large Language Model (LLM) pipeline, serving as the bridge between human-readable text and machine-readable numerical representations. Instead of processing text character-by-character or word-by-word, modern LLMs utilize subword tokenization algorithms. This approach balances the vocabulary size and the sequence length, effectively handling rare words and morphologically rich languages without encountering the Out-Of-Vocabulary (OOV) problem common in traditional word-level tokenization.

The most prevalent algorithm in contemporary models, including the GPT family and LLaMA, is Byte-Pair Encoding (BPE). BPE begins with a base vocabulary of individual characters or bytes. It iteratively counts the frequency of adjacent symbol pairs in the training corpus and merges the most frequent pair into a new, single symbol. This merging process continues until a predefined vocabulary size is reached. For instance, if the pair ("e", "s") is the most frequent, it becomes a new token "es". Subsequently, ("t", "es") might be merged into "tes". This data-driven approach ensures that common words remain as single tokens, while rare words are broken down into meaningful subword units.

Another notable algorithm is WordPiece, predominantly used in BERT. While similar to BPE in its initialization, WordPiece differs in its merging criterion. Instead of simply choosing the most frequent pair, it selects the pair that maximizes the likelihood of the training data when added to the vocabulary. This subtle difference often leads to slightly different subword segmentations optimized for the specific language model objective.

The Unigram language model takes a different approach. It starts with a massive vocabulary and iteratively removes tokens that contribute the least to the overall likelihood of the training corpus. SentencePiece, a popular library, often implements Unigram or BPE directly on raw text, treating spaces as standard characters, which simplifies language-agnostic processing.

Understanding tokenization is crucial because it directly impacts model behavior. For example, LLMs often struggle with character-level tasks, such as spelling a word backward or counting the number of 'r's in "strawberry". This limitation arises because the model does not "see" the individual characters; it only sees the opaque token IDs. Furthermore, tokenization affects arithmetic capabilities, as numbers might be split inconsistently depending on the tokenizer's training data.

References:

1. Hugging Face NLP Course: Tokenizers - https://huggingface.co/learn/nlp-course/chapter2/4
2. OpenAI Tokenizer Documentation - https://platform.openai.com/tokenizer