Tokenization: BPE and SentencePiece

Tokenization is the process of breaking raw text into discrete units called tokens — the atomic pieces that language models actually read and process. It matters because no neural network can operate directly on characters or words; tokenization is the essential translation layer between human language and machine arithmetic. The counterintuitive fact: a single English word like "unbelievable" might become 3–4 tokens, while a single emoji like 🎉 might become 6 tokens — meaning LLMs are often "charged" more to process symbols than entire common words.

The core insight

The core insight is that you need a vocabulary size that is Goldilocks: not so small (character-by-character) that sequences become impossibly long, and not so large (whole-word) that rare words go unrepresented. Byte Pair Encoding (BPE) and SentencePiece both solve this by learning a compression scheme from data — they discover which subword chunks appear together so frequently that it makes sense to treat them as one unit. The "aha moment" is realizing that tokenization is not a linguistic decision — it is a statistical compression decision, and the vocabulary a model learns is as much a hyperparameter as learning rate.

How It Works

Tokenization using BPE proceeds in two distinct phases: training (learning which subword merges to make) and encoding (applying those merges to new text).

Phase 1 — Training BPE

You start with a large corpus of text. Initially, every character is its own token. You then repeatedly find the most frequently co-occurring pair of adjacent tokens and merge them into a single new token. You repeat this for a fixed number of steps, which becomes your vocabulary size.

\quad \text{score}(A, B) = \text{count}(AB) \text{ in corpus}

Explanation: The merge score for a pair (A, B) is simply how many times those two tokens appear side-by-side in the current training corpus — the highest-scoring pair gets merged next. After `k` merge steps, your vocabulary contains the initial character set plus `k` learned merge rules.

\quad |V| = |C| + k

Explanation: The final vocabulary size |V| equals the number of unique starting characters |C| plus the number of merge operations k you performed — so vocabulary size is a direct, controllable hyperparameter. Here is a minimal Python implementation of BPE training: ```python from collections import Counter, defaultdict def get_pairs(vocab): """Count all adjacent symbol pairs across all words.""" pairs = Counter() for word, freq in vocab.items(): symbols = word.split() for i in range(len(symbols) - 1): pairs[(symbols[i], symbols[i+1])] += freq return pairs def merge_vocab(pair, vocab): """Merge the best pair in all words.""" new_vocab = {} bigram = ' '.join(pair) replacement = ''.join(pair) for word, freq in vocab.items(): new_word = word.replace(bigram, replacement) new_vocab[new_word] = freq return new_vocab

# Example corpus (words with space-separated characters, marks word end) vocab = { 'l o w ': 5, 'l o w e r ': 2, 'n e w e s t ': 6, 'w i d e s t ': 3, } num_merges = 10 for i in range(num_merges): pairs = get_pairs(vocab) if not pairs: break best = max(pairs, key=pairs.get) vocab = merge_vocab(best, vocab) print(f"Merge {i+1}: {best} → {''.join(best)}") ``` Running this yields merge steps like: ``` Merge 1: ('e', 's') → es Merge 2: ('es', 't') → est Merge 3: ('n', 'e') → ne ... ```

Phase 2 — Encoding New Text

To encode a new word, you apply the learned merge rules in the order they were learned (most frequent first). This is crucial — order matters. ```python def encode_word(word, merges): """Apply BPE merge rules to a single word.""" symbols = list(word) + [''] for merge_pair in merges: # merges ordered by priority i = 0 while i < len(symbols) - 1: if (symbols[i], symbols[i+1]) == merge_pair: symbols = symbols[:i] + [''.join(merge_pair)] + symbols[i+2:] else: i += 1 return symbols

# Usage merges = [('e','s'), ('es','t'), ('n','e')] # learned order print(encode_word("newest", merges))

# → ['ne', 'w', 'est', ''] ```

SentencePiece: BPE Without Pre-Tokenization

SentencePiece (Google, 2018) makes one critical change: it treats the raw byte stream as input, including spaces, rather than requiring you to split on whitespace first. This matters enormously for languages like Japanese, Thai, or Chinese that have no spaces. ```python import sentencepiece as spm

# Train a SentencePiece model spm.SentencePieceTrainer.train( input='my_corpus.txt', model_prefix='my_tokenizer', vocab_size=8000, model_type='bpe', # or 'unigram', 'char', 'word' character_coverage=0.9995, # cover 99.95% of characters pad_id=0, unk_id=1, bos_id=2, eos_id=3, )

# Load and use sp = spm.SentencePieceProcessor() sp.load('my_tokenizer.model') text = "Tokenization is fascinating!" tokens = sp.encode(text, out_type=str) ids = sp.encode(text, out_type=int) print(tokens) # ['▁Token', 'ization', '▁is', '▁fasci', 'nating', '!'] print(ids) # [142, 891, 23, 4421, 1893, 45] ``` Notice the `▁` (underscore-like) prefix — SentencePiece uses this to mark "token begins after a space," encoding word-boundary information directly in the token string.

researcher · Philip Gage | b. 1960s | Invented Byte Pair Encoding for text compression

Philip Gage was a software engineer who published BPE in 1994 as a lossless data compression algorithm in Dr. Dobb's Journal — not for NLP at all, but for compressing binary data. His specific contribution was the elegant greedy pair-merging scheme: always replace the most frequent byte pair with a single unused byte. The surprising fact: Gage's original algorithm was essentially forgotten until Rico Sennrich re-discovered and adapted it for neural machine translation in 2016, giving a 26-year-old compression trick a second life as the backbone of modern LLM tokenization.

researcher · Rico Sennrich | b. 1986 | Adapted BPE for neural machine translation subword units

Rico Sennrich is a computational linguist and NLP researcher at the University of Edinburgh and later University of Zurich, known for work on neural machine translation. His 2016 paper "Neural Machine Translation of Rare Words with Subword Units" (with Haddow and Birch) directly transplanted Gage's BPE compression idea into NLP, solving the open-vocabulary problem that plagued early seq2seq models. His paper has accumulated over 10,000 citations and is one of the most influential NLP papers of the decade, yet the core algorithm it adapts was written as a C programmer's compression trick in a magazine.

Figure

BPE Training Process — Iterative Pair Merging

Figure

SentencePiece vs Traditional Tokenization

Intuition

The Mental Model

Imagine you're an alien who has just landed on Earth and is trying to learn to read English by studying a massive library of books. You notice that the letters `t`, `h`, `e` appear next to each other constantly — so you decide to treat "the" as a single symbol. Then you notice "ing" always clusters together, and "un" often starts words. You're not thinking about grammar or meaning — you're just finding patterns of co-occurrence and creating shorthand symbols for them. That's exactly what BPE does: it looks at raw frequency in a corpus and greedily builds a vocabulary of high-frequency chunks. SentencePiece then extends this idea by saying: "I won't even assume I know what a word is — I'll treat the whole text as one long stream and let the patterns emerge," which is especially powerful when you move to languages where the concept of a space-separated word doesn't exist.

Historical Development

Origins · 1 minhow this was discovered

History

1994

Philip Gage publishes "A New Algorithm for Data Compression" in Dr. Dobb's Journal, introducing Byte Pair Encoding as a binary compression technique — with no connection to NLP.

2012–2015

Character-level and word-level models dominate NLP; rare and out-of-vocabulary (OOV) words remain a major unsolved problem for neural MT systems using fixed vocabularies.

2016

Rico Sennrich, Barry Haddow, and Alexandra Birch publish "Neural Machine Translation of Rare Words with Subword Units" (ACL 2016), adapting BPE for NLP and demonstrating strong gains on English–German and English–Russian MT benchmarks.

2018

Taku Kudo and John Richardson (Google) publish "SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing," releasing the SentencePiece library that removes all language-specific pre-tokenization assumptions.

2019

OpenAI's GPT-2 uses a byte-level BPE tokenizer with a 50,257-token vocabulary, demonstrating that operating on raw bytes (not characters) can make the tokenizer truly universal across all Unicode text.

2019

BERT (Google) uses WordPiece (a closely related algorithm that uses a likelihood criterion instead of frequency count), with a 30,000-token vocabulary — WordPiece becomes the standard for encoder-only models.

2020

GPT-3 retains byte-level BPE at 50,257 tokens; vocabulary size and tokenizer choice are now recognized as significant architectural decisions rather than engineering afterthoughts.

2023

Llama 2 (Meta) and Mistral use SentencePiece BPE with 32,000 tokens; GPT-4 switches to a new tiktoken-based BPE with ~100,000 tokens, showing vocabulary scaling as an active research area.

2024

Research into "tokenizer-free" models (operating directly on bytes or pixels) grows, but BPE/SentencePiece remain dominant in all major production LLMs including GPT-4o, Gemini, and Claude.

Why It Matters

Real-World Impact

GPT-2 / GPT-3 / GPT-4 (OpenAI)Use byte-level BPE via the `tiktoken` library. GPT-4's tokenizer has ~100,277 tokens and can represent any UTF-8 byte sequence without ever producing an unknown-token — byte-level BPE guarantees this property.

LLaMA / LLaMA 2 / LLaMA 3 (Meta)Use SentencePiece BPE. LLaMA 1 used 32,000 tokens; LLaMA 3 expanded to 128,000 tokens, significantly improving code and multilingual efficiency and reducing sequence lengths for non-English text by up to 30%.

T5 and mT5 (Google)Use SentencePiece with the Unigram Language Model variant (not BPE). mT5 trains a shared 250,000-token SentencePiece vocabulary across 101 languages, making multilingual transfer learning feasible.

BERT and RoBERTa (Google/Facebook)Use WordPiece tokenization (a variant of BPE) with vocabularies of ~30,000 tokens. The `[CLS]` and `[SEP]` special tokens central to BERT's architecture are injected at the tokenizer level, making tokenization inseparable from model architecture.

Code generation models — Codex, GitHub CopilotTokenization quality on code is critical; BPE tokenizers often split variable names and operators in ways that hurt learning. Modern code models use larger vocabularies (50k–100k) or add special tokens for common programming constructs.

Machine Translation production systemsGoogle Translate and DeepL use SentencePiece-based tokenizers as part of their Neural MT pipelines, enabling them to handle any input language without pre-built dictionaries or language-specific preprocessors.

Cost and billingOpenAI charges per token, not per word or character. Because tokenization is language- and content-dependent, non-English users and users sending code are often billed 2–4x more per semantic "unit" than English prose users — a direct economic consequence of tokenizer design.