Theory

Reading time: ~20 minutes (~1500 words) · Prerequisites: Lesson 01 (tokens overview), basic Python

1. The Tokenization Problem

Neural networks operate on numbers, not text. Before a language model can process a sentence, that sentence must be converted into a sequence of integers drawn from a fixed vocabulary. This conversion — tokenization — is deceptively important. It determines the effective sequence length, the model's ability to handle rare words and new languages, and the dollar cost of every API call.

The naive approaches sit at two extremes. Character-level tokenization uses a tiny vocabulary (around 256 entries for UTF-8 bytes) but produces extremely long sequences — the word "tokenization" becomes 12 separate tokens. Long sequences are expensive: attention is quadratic in sequence length, so doubling the number of tokens roughly quadruples the compute in the attention layers. At the other extreme, word-level tokenization keeps sequences short but requires an enormous vocabulary. Any word not seen during training — a typo, a technical term, a word in a new language — becomes an unknown [UNK] token, losing all information.

Subword tokenization resolves this tension. It learns a vocabulary of frequent character sequences — common words stay whole, while rare words are decomposed into recognizable pieces. The word "unhappiness" might become ["un", "happiness"] or ["un", "happ", "iness"], depending on the vocabulary. This means the model can handle any input — even words it has never seen — while keeping sequences reasonably short.

2. Byte Pair Encoding (BPE)

BPE is the most widely used subword algorithm in modern LLMs. It was originally a data compression technique invented by Philip Gage in 1994 and adapted for NLP by Sennrich, Haddow, and Birch in 2016.

Training the Vocabulary

BPE training is a greedy, iterative process:

Initialize the vocabulary with all individual characters (or bytes) that appear in the training corpus, plus an end-of-word marker.
Count all adjacent pairs of tokens across the corpus.
Find the most frequent pair and create a new token by concatenating them.
Replace every occurrence of that pair in the corpus with the new token.
Repeat from step 2 until the vocabulary reaches the target size (e.g., 50,000 or 100,000 tokens).

Each merge step reduces the total number of tokens in the corpus while adding exactly one entry to the vocabulary. The result is a vocabulary where common words are single tokens and rare words are split into frequent subwords.

Encoding (Inference Time)

At inference time, the tokenizer applies the learned merges in the same order they were learned during training. Given a new word, it starts with individual characters and iteratively applies merges from highest to lowest priority. This deterministic process ensures that the same text always produces the same token sequence.

Byte-Level BPE

GPT-2 introduced an important variant: byte-level BPE. Instead of starting from Unicode characters, it starts from the 256 possible byte values. This guarantees that any sequence of bytes — and therefore any UTF-8 encoded text — can be tokenized without falling back to an unknown token. The base vocabulary is always exactly 256 entries, and merges build up from there. GPT-3, GPT-4, and tiktoken's cl100k_base all use byte-level BPE.

3. WordPiece

WordPiece, developed at Google and used in BERT, is closely related to BPE but differs in how it selects which pairs to merge. While BPE greedily picks the most frequent pair, WordPiece selects the pair that maximizes the likelihood of the training data when merged. Concretely, it favors merging pairs where the co-occurrence frequency is high relative to the individual frequencies of the two tokens.

WordPiece uses the ## prefix convention to indicate that a subword is a continuation of a previous token rather than a word start. For example, "tokenization" becomes ["token", "##ization"]. This convention makes it easy to reconstruct the original text by stripping ## prefixes and joining.

4. Unigram and SentencePiece

The Unigram algorithm (Kudo, 2018) takes the opposite approach from BPE. Instead of starting small and merging upward, Unigram starts with a very large candidate vocabulary (often hundreds of thousands of substrings) and iteratively prunes the tokens that contribute least to the overall likelihood of the training data. At each step, it removes a percentage of tokens and re-estimates probabilities using the EM algorithm. The result is a vocabulary where each token has an associated probability, and the tokenizer can find the most probable segmentation of any input.

SentencePiece (Kudo and Richardson, 2018) is not an algorithm but a framework that implements both BPE and Unigram. Its key design decision is treating the input as a raw byte stream with no language-specific pre-tokenization. Where tiktoken and the original BPE implementation split on whitespace and punctuation before applying merges, SentencePiece treats spaces as just another character (represented as the Unicode block character ▁). This makes it truly language-agnostic — it handles Chinese, Japanese, Thai, and other languages that do not use spaces between words just as naturally as English.

SentencePiece is used by T5, Llama, Llama 2, Llama 3, Gemma, and many other open-source models.

5. Special Tokens

Every tokenizer reserves a set of special tokens that are never produced from regular text but carry structural meaning for the model:

[CLS] (BERT): Prepended to every input. Its final hidden state is used as the sequence representation for classification tasks.
[SEP] (BERT): Separates two segments (e.g., question and passage in question-answering).
[PAD]: Fills shorter sequences in a batch to equal length. Masked out in attention so it does not affect computation.
[MASK] (BERT): Replaces tokens during masked language model pre-training.
<|endoftext|> (GPT): Marks the boundary between documents during training and signals the end of generation.
<s> / </s> (Llama, T5): Beginning-of-sequence and end-of-sequence markers.

When estimating token counts for API cost, remember that special tokens are added automatically by the API — they are not visible in your input string but still count toward your usage.

6. Token Embeddings

Once text is tokenized into integer IDs, each ID is mapped to a dense vector through an embedding lookup table — a simple matrix of shape (vocab_size, hidden_dim). For a model with a 100K vocabulary and 4096-dimensional hidden states, this table alone contains 409 million parameters.

These embeddings are learned during pre-training. Tokens with similar meanings or usage patterns end up with similar vectors. The embeddings are then summed with positional encodings (which encode where in the sequence each token sits) before being fed into the transformer layers.

Many models use weight tying: the same embedding matrix is shared between the input embedding layer and the output prediction layer. This reduces total parameter count and has been shown to improve performance, especially for smaller models.

7. Multilingual Efficiency and Cost

Tokenizer vocabulary is learned from training data, which for most large models is predominantly English. This creates a systematic efficiency gap: English text is tokenized compactly (roughly 1 token per word), while languages with different scripts require significantly more tokens to express the same meaning.

Hindi text, for example, can require 3–5x more tokens than semantically equivalent English text when using a tokenizer like cl100k_base. This directly translates to higher API costs and faster context window exhaustion for non-English users — effectively making the model more expensive for the populations that can least afford it.

Newer models are addressing this. Llama 3's tokenizer expanded its vocabulary from 32K to 128K tokens, with deliberate inclusion of multilingual data during vocabulary training. This reduced token counts for non-English languages by 15–40% compared to Llama 2. Similarly, modern tokenizers trained on balanced multilingual corpora show much better efficiency across languages.

Practical Takeaway

If you are building a multilingual application, always benchmark token counts across your target languages before committing to a model. The tokenizer — not the model architecture — may be the biggest factor in your per-language costs.

8. Key Concepts Summary

Concept	What it means	Why it matters
BPE	Bottom-up subword merging by frequency	Most common tokenization algorithm in LLMs
WordPiece	Likelihood-based merging (BERT)	Used in BERT and many encoder models
Unigram	Top-down vocabulary pruning	Produces probabilistic segmentations
SentencePiece	Language-agnostic tokenization framework	No pre-tokenization needed; best for multilingual
Special tokens	Structural markers added by the tokenizer	Control model behavior; count toward usage
Token embeddings	Learned vector representations of tokens	Bridge from discrete IDs to continuous space
Multilingual efficiency	Token count varies by language and tokenizer	Directly impacts cost and context window usage