Tokens & Context Windows

Byte Pair Encoding (BPE)

Philip Gage published a short article in C Users Journaldescribing a data compression algorithm that would, two decades later, become the foundation of how every major LLM reads text. The algorithm is elegant in its simplicity:

1. Start with a vocabulary of individual bytes (256 symbols)
2. Count all adjacent pairs of symbols in the training corpus
3. Merge the most frequent pair into a new symbol
4. Repeat until vocabulary reaches desired size (e.g., 50,000)

# BPE in action: learning merges from corpus
# Starting vocabulary: all individual characters
# Corpus: "low lower lowest low low lower"

# Iteration 1: most frequent pair is ('l', 'o') → merge into 'lo'
# Iteration 2: most frequent pair is ('lo', 'w') → merge into 'low'
# Iteration 3: most frequent pair is ('e', 'r') → merge into 'er'
# Iteration 4: most frequent pair is ('low', 'er') → merge into 'lower'
# ...continue until vocab_size reached

# Result: "unbelievable" → ["un", "believ", "able"]
# All three subwords reusable across the vocabulary!

Gage's algorithm was designed for file compression, not NLP. It would take 21 years before anyone thought to apply it to machine translation.

Sennrich: BPE for Neural Machine Translation

Rico Sennrich, Barry Haddow, and Alexandra Birch at the University of Edinburgh had a breakthrough insight: BPE's compression algorithm could solve the open-vocabulary problem in neural machine translation. Instead of compressing bytes, apply it to characters in a text corpus. The resulting subword vocabulary sits in the sweet spot between characters and words — small enough to be tractable (32K–100K tokens), rich enough to preserve meaning, and capable of representing any string, even words never seen in training.

This single paper changed everything. Within three years, every major NLP system adopted subword tokenization. GPT-1, GPT-2, GPT-3, RoBERTa — all use BPE. The idea that LLMs process "subword tokens" rather than words or characters traces directly to Sennrich 2015.

SentencePiece: Language-Agnostic Tokenization

Taku Kudo and John Richardson at Google released SentencePiece, solving a critical limitation of BPE: it assumed pre-tokenized (whitespace-split) input, which doesn't work for languages like Chinese, Japanese, and Thai that don't use spaces between words.

SentencePiece treats the input as a raw byte stream — no language-specific pre-processing required. It implements both BPE and a new algorithm called Unigram Language Model(Kudo, 2018), which starts with a large vocabulary and prunes it down using a likelihood-based criterion rather than greedily merging pairs.

# SentencePiece: works on raw text, any language
import sentencepiece as spm

# Train a tokenizer from raw corpus
spm.SentencePieceTrainer.train(
    input='corpus.txt',
    model_prefix='my_tokenizer',
    vocab_size=32000,
    model_type='unigram'  # or 'bpe'
)

sp = spm.SentencePieceProcessor(model_file='my_tokenizer.model')

# Works on any language without pre-tokenization
sp.encode("Hello world", out_type=str)     # ['▁Hello', '▁world']
sp.encode("東京は晴れです", out_type=str)    # ['▁東京', 'は', '晴れ', 'です']
sp.encode("Привет мир", out_type=str)      # ['▁При', 'вет', '▁мир']
# The ▁ (U+2581) marks word boundaries

SentencePiece became the tokenizer of choice for multilingual models. T5, LLaMA, Gemma, and Mistral all use SentencePiece. BERT used a related algorithm called WordPiece (Schuster & Nakajima, 2012), which is similar to BPE but selects merges by maximizing likelihood rather than frequency.

GPT-2 & Byte-Level BPE

OpenAI's GPT-2 introduced byte-level BPE: instead of starting from characters (which vary by encoding), start from the 256 raw bytes of UTF-8. This guarantees that any byte sequence can be tokenized — no <UNK> token needed, ever. Every OpenAI model since (GPT-3, GPT-4, GPT-5) uses this approach, implemented in the open-sourcetiktoken library.

— Radford, A. et al. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Technical Report.