Tokenization
How does the tokenization pipeline transform raw Unicode text into integer tensors for neural network consumption?
How this lesson unfolds.
Begin with How does the tokenization pipeline transform raw Unicode text into integer tensors for neural network consumption?. Follow the visual diagrams to build an intuitive mental model.
How does the subword tokenization pipeline balance sequence length against vocabulary size to convert raw text into neural inputs?
Imagine packing a shipping container with household goods. If you pack every grain of rice individually (character-level), the inventory list has billions of items and tracking them is impossibly slow. If you insist on only packing fully assembled multi-room houses in single giant crates (word-level), you need an infinite warehouse and any custom bungalow cannot be shipped at all. Subwords are modular furniture: small, reusable units like drawers, table legs, and panels that cleanly assemble any conceivable room while keeping both the parts catalog and the inventory list compact.
- Learning goalAnalyze the structural tradeoffs of the subword tokenization pipeline to balance vocabulary size against sequence length using Pareto-optimal partitioning.
- Helpful foundationsUnicode and UTF-8 encoding standards · Neural Machine Translation of Rare Words with Subword Units (Sennrich et al., 2015)
- Common trapBelieving that tokenization simply splits sentences by whitespace. Whitespace splitting fails entirely on non-segmented languages like Mandarin or Japanese, chokes on punctuation, and fails to handle morphological compounds.
- Next connectionNext, examine the exact algorithmic mechanics, bigram frequency counting, and step-by-step vocabulary expansion in Part B.
More context & mechanics
The subword tokenization pipeline transforms raw human language into model-ready tensors across three distinct structural tiers:
- Character-Level Extreme: With an alphabet of ~256 bytes, vocabulary size is minimal, but the sequence length blows up by 4× to 5×. Because transformer attention scales quadratically (O(T²)), this bloat severely caps effective context windows.
- Word-Level Extreme: Storing every inflected word form ("running", "runner", "runs") causes vocabulary size |V| to explode past millions of entries, triggering catastrophic out-of-vocabulary (OOV) failures on compound or misspelled words.
- Subword Pareto Frontier: Byte Pair Encoding (BPE) identifies the mathematical sweet spot. Common words ("the", "cat") remain intact single tokens, while rare words ("unhappiness") are seamlessly partitioned into frequent sub-components: `["un", "happi", "ness"]`.
In production architectures like GPT-4 and Llama-3, vocabulary sizes are tuned between 50,257 and 128,256 tokens. This strikes the exact operational equilibrium where average compression is roughly 0.75 words per token (~4 characters per token), keeping sequence lengths short enough for ultra-fast GPU matrix operations while eliminating out-of-vocabulary fallback errors entirely.
Philip Gage initially invented Byte Pair Encoding in 1994 as a heuristic data compression algorithm. Two decades later, in 2015, Rico Sennrich, Barry Haddow, and Alexandra Birch adapted BPE to Neural Machine Translation, demonstrating that subword decomposition completely eliminated the dreaded `<UNK>` token barrier in natural language processing.
- Modular blocks over dust and boulders: Characters are dust, whole words are boulders; subwords are the brickwork of machine cognition.
- Pareto Tradeoff: Small vocabularies inflate sequence lengths; giant vocabularies trigger out-of-vocabulary amnesia.
How does Byte Pair Encoding iteratively extract greedy argmax character bigrams to construct a deterministic vocabulary?
Think of a mint printing currency. If people constantly trade pairs of \1 bills together for small snacks, the central bank notices the high velocity of this specific pair and prints a dedicated \2 bill. If the combination of a \2 bill and a \1 bill becomes overwhelmingly popular, the bank issues a \3 coin. By greedily minting denominations for whatever combinations change hands most often, the total number of transactions needed to settle payments drops dramatically.
- Learning goalCompute greedy argmax bigram frequencies across a corpus and derive iterative vocabulary expansion steps using the BPE algorithm.
- Helpful foundationsBPE subword pipeline fundamentals · Hash map dictionary counting in Python
- Common trapAssuming that BPE merges are dynamic at inference time. BPE merge rules are frozen during offline vocabulary training; inference simply replays the fixed, ranked merge table greedily.
- Next connectionWith subwords extracted, explore why subword tokens are essential for handling rare words and multilingual vocabularies in Chapter 7 Screen 2.
More context & mechanics
The BPE vocabulary construction algorithm operates via deterministic greedy contraction:
- Pair Frequency Metric:
Let the corpus be represented as token sequences sₖ. The co-occurrence frequency of adjacent bigram (tᵢ, t_(i+1)) is:
c(tᵢ, t_(i+1)) = ∑_(k=1)^N I(sₖ == (tᵢ, t_(i+1)))
- Greedy Argmax Selection:
At iteration m, the algorithm identifies the most frequent adjacent pair:
(t_a, t_b)^* = argmax_((tᵢ, tⱼ)) c(tᵢ, tⱼ)
- Vocabulary Expansion Rule:
The winning bigram is concatenated into a new single atomic token and appended to the vocabulary:
V_(m+1) = Vₘ ∪ (t_a, t_b)^*
Given a toy corpus:
- 5 occurrences of `"low"` → `['l', 'o', 'w']`
- 2 occurrences of `"lower"` → `['l', 'o', 'w', 'e', 'r']`
- 6 occurrences of `"newest"` → `['n', 'e', 'w', 'e', 's', 't']`
- 3 occurrences of `"widest"` → `['w', 'i', 'd', 'e', 's', 't']`
Initial character alphabet: V₀ = d, e, i, l, n, o, r, s, t, w (|V₀| = 10).
- Step 1: Bigram `('e', 's')` occurs in `"newest"` (6×) and `"widest"` (3×). Total frequency = 6 + 3 = 9 (highest in corpus). Merge `('e', 's')` → `'es'`. New vocabulary |V₁| = 11.
- Step 2: Bigram `('es', 't')` occurs in `"newest"` (6×) and `"widest"` (3×). Total frequency = 6 + 3 = 9. Merge `('es', 't')` → `'est'`. New vocabulary |V₂| = 12.
- Step 3: Bigram `('l', 'o')` occurs in `"low"` (5×) and `"lower"` (2×). Total frequency = 5 + 2 = 7. Merge `('l', 'o')` → `'lo'`. New vocabulary |V₃| = 13.
Production tokenizers like OpenAI's `tiktoken` execute BPE using optimized priority queues and hash tables in Rust. By processing multi-gigabyte training corpora in parallel across dozens of CPU cores, `tiktoken` extracts 100k merges in minutes, ensuring zero runtime bottleneck during preprocessing.
The mathematical formulation of recursive dictionary-based text compression originates from Abraham Lempel and Jacob Ziv (LZ77/LZ78), which Philip Gage streamlined into BPE in 1994. Its adaptation by Sennrich in 2015 proved that statistical frequency counts alone suffice to discover natural linguistic morphemes without requiring handcrafted grammatical parsers.
- Count pairs, take the argmax, contract the sequence: The three-beat rhythm of BPE vocabulary building.
- Argmax greedy consensus: The most frequent adjacent pair earns the right to become an atomic symbol.
Why do subword algorithms (Byte Pair Encoding) strike the optimal mathematical tradeoff between word-level and character-level tokenization?
Imagine packing luggage for a global trip. Method 1 (Word-Level) is packing 100,000 pre-assembled complete outfits in giant shipping containers: every time you encounter an unfamiliar jacket or foreign garment, you fail with an 'Out-Of-Vocabulary' error. Method 2 (Character-Level) is packing only individual threads and sewing needles: you have a tiny 26-letter toolkit with 0% OOV, but sewing a simple t-shirt takes 50,000 tedious stitches (sequence length explodes 5x to 10x, diluting attention). Method 3 (Subword BPE) packs pre-made modular fabric pieces (sleeves, collars, zippers): common words are 1 piece, rare words are quickly snapped together from 2 or 3 pieces, keeping sequence lengths compact and vocabulary bounded.
- Learning goalEvaluate the mathematical tradeoffs between sequence length T, vocabulary size |V|, and Out-Of-Vocabulary rate across word, character, and subword tokenization schemes.
- Helpful foundationsCombinatorics and sequence length scaling · Zipf's law in natural language corpora · Subword Neural Machine Translation (Sennrich et al., 2015)
- Common trapBelieving that character-level models are better because they have tiny vocabularies (|V| ~ 256). While character vocabularies are small, transformer self-attention computational complexity is O(T²) in sequence length; multiplying sequence length T by 5x increases attention compute by 25x, making character-level models prohibitively expensive.
- Next connectionEven with subword algorithms, what happens when the tokenizer encounters unknown Unicode symbols, rare alphabets, or non-Latin text? That is the role of byte-level tokenization.
More context & mechanics
Comparing the three tokenization paradigms:
| Metric | Word-Level | Character-Level | Subword BPE (Hybrid) |
| :--- | :--- | :--- | :--- |
| Vocabulary Size (|V|) | Huge (10⁵ to 10⁶) | Tiny (10², e.g. 256) | Moderate (3 × 10⁴ to 10⁵) |
| Sequence Length (T) | Shortest (1.0×) | Longest (4.5× to 6.0×) | Compact (1.2× to 1.4×) |
| Attention Compute (O(T²)) | Baseline (1.0×) | Massive (20× to 36×) | Efficient (1.5× to 2.0×) |
| Out-of-Vocabulary (OOV) | High (unseen words → `<unk>`) | Zero (all characters known) | Zero (falls back to subwords/bytes) |
| Semantic Density / Token | High | Extremely Low | Optimal |
Subword BPE applies a frequency-driven merge rule:
Score(c₁, c₂) = Freq(c₁ c₂)
Frequent words (`"the"`, `"learning"`) remain a single token ID. Rare words (`"unconstitutionality"`) split into frequent subword components: `["un", "constitution", "ality"]`.
Virtually every modern LLM uses subword tokenization: GPT-2/3/4 uses BPE (|V| = 50,257 / 100,277), Llama 3 uses tiktoken BPE (|V| = 128,256), and Gemma uses SentencePiece BPE (|V| = 256,000).
Before 2015, NLP systems routinely suffered from the `<unk>` crisis: any medical, technical, or misspelt word was mapped to an unknown token, causing translation models to produce broken sentences. Sennrich et al. introduced BPE to solve this forever.
- Words explode the vocabulary; characters explode the sequence; subwords balance both.
- Frequent words stay whole; rare words break into familiar pieces.
How does Byte-Level Byte Pair Encoding (BBPE) eliminate the Out-Of-Vocabulary `<unk>` problem across arbitrary Unicode data?
Think of an old English typewriter that lacks the key for the Greek letter pi or an emoji like 🚀—it jams and prints a black square box (<unk>). In early NLP, encounter an unfamiliar word and the model was blinded. Modern LLMs (starting with GPT-2's Byte-Level BPE) eliminate the <unk> token entirely by basing their vocabulary on the 256 fundamental raw bytes (0x00 through 0xFF) of UTF-8 encoding. Even if you type an alien emoji or an ancient Egyptian hieroglyph never seen during training, it is decomposed into 4 raw UTF-8 bytes that the model processes without crashing.
- Learning goalImplement Byte-Level Byte Pair Encoding (BBPE) and prove why initializing vocabulary with 256 base byte tokens guarantees a 0% Out-Of-Vocabulary (OOV) rate.
- Helpful foundationsUTF-8 byte encodings (1-byte to 4-byte variable encoding) · Language Models are Unsupervised Multitask Learners / GPT-2 (Radford et al., 2019)
- Common trapAssuming that GPT-2 and GPT-4 have an <unk> token in their vocabulary. Modern byte-level BPE tokenizers (like OpenAI's tiktoken) have no <unk> token at all; every valid or invalid UTF-8 byte sequence can be represented unambiguously as an integer token.
- Next connectionBeyond semantic text and raw bytes, a neural network needs administrative signals to manage conversations and document boundaries: special control tokens.
More context & mechanics
In standard Unicode, there are over 149,000 defined characters across hundreds of scripts. Initializing a vocabulary with all Unicode characters would cause vocabulary explosion.
Byte-Level BPE solves this elegantly:
- UTF-8 Byte Representation:
Every Unicode character is encoded as 1 to 4 raw bytes (0x00 to 0xFF).
For example, the rocket emoji 🚀 is encoded in UTF-8 as four bytes:
🚀 ⟹ [0xF0, 0x9F, 0x9A, 0x80]
- Base Vocabulary Initialization:
Initialize vocabulary V with the 256 possible byte values:
V₀ = 0, 1, 2, ṡ, 255
- Iterative Pair Merging:
Run BPE merge rules over byte sequences. If the byte sequence [0xF0, 0x9F, 0x9A, 0x80] is common in the training corpus, BPE merges it into a single token ID. If an emoji is rare, it is processed as 4 individual byte tokens.
Because every digital file is a sequence of bytes ∈ [0, 255], the Out-Of-Vocabulary rate is mathematically zero:
OOV Rate ≡ 0.0\%
Byte-Level BPE enables LLMs to process programming languages, binary file dumps, hexadecimal strings, mathematical symbols, and multilingual text without specialized preprocessors or out-of-vocabulary crashes.
OpenAI adopted Byte-Level BPE in GPT-2 (2019). Radford et al. showed that byte-level modeling avoided the need for complex pre-tokenization rule engines across different languages, providing a clean foundation for universal tokenization.
- 256 base bytes can build every character in human history.
- No `<unk>`, no crashes: every byte has a home.
How do special control tokens (`<|endoftext|>`, `<|pad|>`, `<|im_start|>`) structure multi-turn dialogues and enforce document boundaries?
Imagine an orchestra performing a symphony. The musicians don't just read musical notes (A, B, C#); they also watch the conductor's baton for non-musical commands: 'Silence / Rest', 'Turn page', and 'End of movement'. Reserved delimiter flags are the conductor's baton for an LLM: <|endoftext|> tells the model the current book is over so it doesn't bleed characters into the next document; <|im_start|>user tells it that a human is speaking, and <|im_start|>assistant triggers it to formulate its response.
- Learning goalConfigure and manipulate special control tokens for sequence boundary delineation, batch padding, and multi-turn conversational chat templating.
- Helpful foundationsSequence padding and attention masks · Chat template syntax (ChatML, Jinja2)
- Common trapThinking that special tokens like <|endoftext|> are tokenized as individual punctuation characters (<, |, endoftext, |, >). Special tokens are registered as atomic, unbreakable units in the tokenizer dictionary with their own unique integer IDs (e.g. 50,256 in GPT-2) and bypass normal subword splitting.
- Next connectionNow that we can convert text into an unbroken stream of integer token IDs, Lesson 9 demonstrates how to slice this stream into sliding window input-output pairs for training.
More context & mechanics
Special tokens act as non-semantic boundary markers and state delimiters:
- Document Delimiters (`<|endoftext|>`):
Prevents cross-contamination during pretraining. Concatenating Document A and Document B:
X = [Doc A tokens] ⊕ [⟨|endoftext|⟩] ⊕ [Doc B tokens]
During inference, emitting `<|endoftext|>` signals the autoregressive generation loop to halt.
- Batch Alignment Padding (`<|pad|>`):
In batched tensor training, sequences of unequal length are padded to max length T_(max):
X_(padded) = [t₁, t₂, ṡ, tₖ, PAD, PAD]
Attention masks M_(i, j) = -∞ ensure padded tokens receive 0 attention weight and contribute zero loss.
- Turn-Based ChatML Markers:
⟨|im\_start|\rangleuser\backslash nExplain gravity.⟨|im\_end|⟩\backslash n⟨|im\_start|\rangleassistant\backslash n
These control tokens explicitly condition the causal transformer's attention on the current speaker role.
Production inference APIs (OpenAI, Anthropic, vLLM) utilize stop-token parameters:
`stop=["<|endoftext|>", "<|im_end|>"]`
When the generator predicts this token ID, the inference engine immediately cuts off the streaming response and closes the websocket.
Early models like BERT used `[CLS]` and `[SEP]` for classification and sentence pairs. OpenAI introduced `<|endoftext|>` in GPT-2 (token ID 50256), and ChatML formalized role delimiters (`<|im_start|>`, `<|im_end|>`) in 2022 to prevent prompt injection attacks.
- Ordinary tokens communicate content; control tokens enforce structure.
- `<|endoftext|>` halts the pen; role tokens switch the speaker.
Why do Large Language Models struggle with simple character-level tasks like spelling 'strawberry' or reversing strings, and how does subword chunking explain this behavior?
Imagine reading a book written not in letters, but using a collection of 50,257 pre-printed rubber stamps. One stamp prints 'cat', another prints 'straw', another prints 'berry'. If someone asks you: 'How many letters r are on that page?', you can't simply count the stamps—you only see the stamps as indivisible symbols! To an LLM, the word 'strawberry' is not an 11-letter string ['s','t','r','a','w','b','e','r','r','y']. To the model, it is a sequence of just 3 atomic numbers: [4999, 1021, 23512]. The transformer never touches individual letters.
- Learning goalAnalyze how subword segmentation creates character-blind representation vectors and quantify the computational quadratic savings of token chunking.
- Helpful foundationsNeural Machine Translation of Rare Words with Subword Units / BPE (Sennrich et al., 2015) · SentencePiece: A simple and language independent subword tokenizer (Kudo & Richardson, Google, 2018) · Byte-Level BPE in Language Models (Radford et al., OpenAI GPT-2, 2019)
- Common trapAssuming LLMs 'see' raw ASCII letters like humans do. LLMs never see characters; they receive high-dimensional embedding vectors corresponding to multi-character token IDs.
- Next connectionNow that we understand how text is partitioned into integer token IDs, the immediate next hurdle is geometric: how do discrete integers become continuous coordinates? That bridge is crossed in Chapter 02: Token Embeddings.
More context & mechanics
A tokenizer maps text string S to a sequence of discrete integers T:
Tokenizer(S) = [t₁, t₂, ṡ, t_N], tᵢ ∈ 0, 1, ṡ, |V|-1
In the OpenAI `cl100k_base` vocabulary (|V| = 100,277):
"strawberry" →(BPE) ["str", "aw", "berry"] ⟹ [4999, 1021, 23512]
Toy Numerical Trace: The self-attention matrix compares token pairs:
Attention Matrix Size = N_(tokens) × N_(tokens) = 3 × 3 = 9 elements
If the model operated at the raw character level (11 characters):
Character Matrix Size = 11 × 11 = 121 elements
Subword chunking achieves a 121/9 ≈ 13.44× compute reduction! However, the hidden state h₃ ∈ R^(d) corresponds to the token `"berry"`. Asking the model to count the occurrences of `"r"` forces it to guess from latent associations rather than directly evaluating the indicator function:
Count(c) = ∑_(j=1)^(11) I(sⱼ == c)
Explains classic frontier model failure modes: counting letters in words, solving anagrams, reversing strings, and performing digit-by-digit column arithmetic. Modern multimodal and code models increasingly use byte-level tokenizers or add explicit character-level reasoning scratchpads (Chain-of-Thought) to bypass this tokenization blind spot.
Byte Pair Encoding was adapted for NLP by Rico Sennrich et al. in 2016 ('Neural Machine Translation of Rare Words with Subword Units'). While solving the out-of-vocabulary dilemma, it introduced the linguistic granularity mismatch that still affects modern LLMs.
- LLMs think in token chunks, not character strokes.
- Efficiency in sequence length is paid for with blindness to internal spelling.
How does subword tokenization reconcile the trade-off between massive out-of-vocabulary vocabularies and sequence length explosion?
Imagine sending a telegram where each distinct dictionary word requires a bulky wooden printing block. If you use word-level printing, you need a warehouse of 1,000,000 blocks; the moment someone uses a rare slang word or misspellings like 'unbelievablyyy', your printer fails completely with an 'Unknown Word' stamp. If you switch to individual letters (character-level), your printing kit needs only 26 blocks, but a single telegram explodes from 10 blocks to 60 blocks long, costing a fortune in transmission fees and making sentences painfully slow to read. Subword tokenization is like building interchangeable syllables: common words get their own single stamp, while rare words are assembled from familiar prefixes, roots, and suffixes like 'un-' + 'believ' + '-able'. You keep your warehouse small (50,000 stamps) while guaranteeing you can print every word in the English language without ever failing.
- Learning goalEvaluate the architectural trade-offs between word-level, character-level, and subword tokenization across vocabulary size and sequence length.
- Helpful foundationsText tokenization concepts · Self-attention quadratic complexity O(T²)
- Common trapAssuming subword tokenizers split words strictly along grammatical syllable boundaries. Subword tokenizers operate on purely statistical string co-occurrence frequencies without intrinsic linguistic or morphological rules.
- Next connectionNext, examine the algorithmic mechanics of BPE merge tables and greedy argmax pair extraction in Screen 07-001B.
More context & mechanics
Natural language processing architectures must convert continuous text into discrete numerical identifiers:
- The Three Vocabulary Granularity Regimes:
- Word-Level Tokenization: Vocabulary size V > 1,000,000. While sequence length T is short, the embedding matrix becomes astronomical (V × d_(model)), and unseen words trigger fatal `<UNK>` (out-of-vocabulary) tokens.
- Character-Level Tokenization: Vocabulary size V ≈ 256 (ASCII bytes). While `<UNK>` is eliminated, sequence length T expands by 4× to 6×. Because transformer self-attention scales quadratically O(T²), this crashes GPU VRAM.
- Subword Tokenization (The Golden Mean): Vocabulary size V ≈ 50,257 (GPT-2) to 128,256 (LLaMA-3). Sequence lengths remain compact while frequent morphemes are cleanly decomposed.
- The Morphological Decomposition Pipeline:
Rare and compound words decompose into meaningful subword roots:
"unbelievable" ⟶ "un" (295), "believ" (4192), "able" (481)
Semantic and syntactic relationships are preserved across morphological variants.
- Compression Ratio Metrics:
On standard English corpora:
100 Words ≈ 133 Subword Tokens ≈ 500 Characters
Yielding an average subword efficiency of ≈ 0.75 words per token or ≈ 4 characters per token.
Standard across modern LLMs: Byte-Pair Encoding (BPE) in GPT-2/GPT-4/LLaMA, WordPiece in BERT, and Unigram in SentencePiece for multilingual T5.
Rico Sennrich, Barry Haddow, and Alexandra Birch adapted Philip Gage's 1994 data compression algorithm (Byte-Pair Encoding) to neural machine translation in 2016, solving the long-standing open-vocabulary translation problem.
- Words blow up vocabulary; characters blow up attention: Subwords balance the funnel.
- Four characters per token: The universal empirical rule of thumb for English subword compression.
What is the mathematical foundation and geometric intuition of BPE Merge Frequency: Dynamic Sequence Contraction?
Understand BPE Merge Frequency: Dynamic Sequence Contraction visually: Counting pair frequencies requires updating the token sequence after each merge.. Every transformation preserves core structural invariants while mapping coordinate spaces.
- Learning goalMaster the algebraic and geometric derivation of BPE Merge Frequency: Dynamic Sequence Contraction.
- Helpful foundationsLinear Algebra Fundamentals · Matrix Transformations · Vector Spaces
- Common trapAssuming BPE Merge Frequency: Dynamic Sequence Contraction is merely a computational trick rather than an invariant spatial law.
- Next connectionConnects to upstream spectral theory and downstream tensor operations.
More context & mechanics
An educational algorithmic correction diagram on natural warm linen (#f5f4e9) with a 1px slate frame (#cbd5e1).
Top section: Title in bold sans-serif: "BPE Merge Frequency: Dynamic Sequence Contraction". Subtitle in serif: "Counting pair frequencies requires updating the token sequence after each merge."
Middle section: Concrete walkthrough on training corpus: ("h u g": 10), ("p u g": 5), ("p u n": 12), ("h u g s": 5).
Step 1: Bigram ('u', 'g') appears 10 + 5 + 5 = 20 times. Wins and merges to atomic token 'ug'.
Corpus after Step 1: ("h ug": 10), ("p ug": 5), ("p u n": 12), ("h ug s": 5).
Step 2 Evaluation Table:
- Bigram ('p', 'u'): Only exists in "p u n" = 12 occurrences (in "p ug", 'u' is already merged into 'ug'!).
- Bigram ('h', 'ug'): Appears in "h ug" (10) and "h ug s" (5) = 15 occurrences!
Highlight with green badge: "Step 2 Winner: ('h', 'ug') with 15 occurrences (15 > 12) -> merges to 'hug'".
Bottom section: Error Warning Box: "Common Bug: Never count pair frequencies from un-contracted raw strings; once tokens merge, their sub-characters are no longer atomic pairs."
Crisp tabular layout, generous whitespace, clear colored highlights.
This principle is foundational across deep learning optimization, high-dimensional representation, and modern LLM architectures.
"BPE Merge Frequency: Dynamic Sequence Contraction: Invariance and structure determine stability under spatial and numerical transformations."
How does normalizing non-negative empirical count frequencies project raw data onto the probability simplex?
Imagine rolling a 6-sided die 100 times. You tally the results: 1 came up 10 times, 2 came up 20 times, 3 came up 30 times, and 4, 5, 6 came up 10, 15, and 15 times. These raw counts [10, 20, 30, 10, 15, 15] sum to 100. To turn these tallies into probabilities, you simply divide each count by 100: [0.10, 0.20, 0.30, 0.10, 0.15, 0.15]. The counts have been mapped onto a flat triangular geometric surface called the probability simplex, where all coordinates are positive and their sum is guaranteed to be 1.0.
- $$Divide observation frequencies c_i by total count N to yield probability vector p on the standard simplex Delta^(K-1).$$
- Learning goalMap discrete integer frequency counts onto the standard probability simplex and verify the partition of unity.
- Helpful foundationsHigh-school arithmetic · Théorie analytique des probabilités (Laplace, 1812)
- Common trapAssuming unnormalized counts can be compared directly across datasets of different sizes; normalization is essential to make probability statements independent of sample scale.
- Next connectionWhen multiplying thousands of small probabilities together in long sequences, numbers crash to zero; how do logarithms shield against this underflow? We examine the logarithm shield.
More context & mechanics
Given a discrete observation vector c = [c₁, c₂, ṡ, c_K]^T ∈ Z_(≥ 0)^K with total count N = ∑_(i=1)^K cᵢ > 0:
The empirical categorical probability estimator is:
pᵢ = cᵢ/N = (cᵢ) / (∑_(j=1)^K cⱼ)
The resulting probability vector p = [p₁, ṡ, p_K]^T lies on the standard (K-1)-simplex:
Δ^(K-1) = p ∈ R^K | pᵢ ≥ 0, ∑_(i=1)^K pᵢ = 1
Geometric properties:
- Convexity: Any convex combination of probability vectors on Δ^(K-1) remains on Δ^(K-1).
- Dimension: A K-outcome categorical distribution requires only K-1 degrees of freedom because p_K = 1 - ∑_(i=1)^(K-1) pᵢ.
In subword tokenization (BPE and WordPiece), vocabulary frequency tables count adjacent character pairs. The greedy merge decision picks the pair maximizing the empirical frequency count c(u, v) across the training corpus.
Pierre-Simon Laplace formalized the classical definition of probability as the ratio of favorable cases to total possible cases in 1812 in 'Théorie analytique des probabilités'.
- Divide each count by the grand total.
- The simplex is the flat geometric slice where probabilities sum to 1.
How do UTF-8 prefix bitmasks encode variable-length Unicode code points across 1 to 4 raw bytes?
Imagine sending telegram messages where some words are short and some are long, but there are no spaces between words! How does the receiver know where one word stops and the next begins? UTF-8 solves this with leading traffic lights: if a byte starts with `0`, it is a solo 1-byte character (standard ASCII). If it starts with `110`, it announces: 'I am a 2-byte character!' If it starts with `1110`, it announces 3 bytes; and `11110` announces 4 bytes. Any continuation byte always starts with `10`. You can drop into the middle of any byte stream and immediately know where you are.
- Learning goalDecode variable-length UTF-8 bit patterns into numerical Unicode code points using bitwise masking and shifting.
- Helpful foundationsBinary bitwise operations · UTF-8, a transformation format of ISO 10646 (RFC 3629)
- Common trapAssuming UTF-8 characters are always 1 byte; non-English characters take 2 to 4 bytes, which is why byte-level tokenizers must operate on byte representations.
- Next connectionWhy does operating on raw bytes completely eliminate out-of-vocabulary words? We examine the death of the unknown token.
More context & mechanics
UTF-8 partitions the Unicode codespace into four bitmask templates:
- 1-Byte (U+0000 to U+007F, ASCII):
- Format: `0xxxxxxx` (7 data bits, 128 characters)
- 2-Byte (U+0080 to U+07FF):
- Format: `110xxxxx 10xxxxxx` (11 data bits, 2,048 characters)
- 3-Byte (U+0800 to U+FFFF, Asian scripts):
- Format: `1110xxxx 10xxxxxx 10xxxxxx` (16 data bits, 65,536 characters)
- 4-Byte (U+10000 to U+10FFFF, Emojis & rare scripts):
- Format: `11110xxx 10xxxxxx 10xxxxxx 10xxxxxx` (21 data bits, 2,097,152 characters)
Bitwise extraction of code point U from a 2-byte sequence [b₁, b₂]:
U = ((b₁ \& 0x1F) ≪ 6) \vert (b₂ \& 0x3F)
The continuation prefix `10` guarantees self-synchronization: a corrupt or dropped byte cannot cause cascading desynchronization beyond 4 bytes.
Modern tokenizers like OpenAI's `tiktoken` process raw UTF-8 byte streams directly in Rust before running regex pre-tokenization, enabling universal multi-lingual parsing.
Ken Thompson and Rob Pike designed UTF-8 on a placemat in a New Jersey diner in September 1992 for the Plan 9 operating system, replacing incompatible multi-byte encodings worldwide.
- Count the leading ones to know the byte length.
- Continuation bytes always start with 10.
How does initializing tokenization vocabularies with the 256 fundamental byte values guarantee zero out-of-vocabulary errors?
In older NLP models, whenever a user typed a rare symbol, an ancient hieroglyphic, or a brand-new emoji like 🦄, the model threw its hands up in despair and replaced the word with `<UNK>` (Unknown). If `<UNK>` appeared, the sentence was ruined. Byte-level BPE solved this forever with an ingenious insight: every file, image, emoji, and word on any computer is just a sequence of 8-bit bytes (0 to 255). By including all 256 raw byte tokens in the base dictionary, the model can spell out literally ANY digital sequence in existence. The `<UNK>` token was permanently banished to the history books.
- Learning goalProve that a byte-level base vocabulary guarantees complete coverage of arbitrary Unicode text without unknown tokens.
- Helpful foundationsUTF-8 byte representations · Language Models are Unsupervised Multitask Learners (Radford et al., 2019)
- Common trapBelieving byte-level BPE makes sequences 4x longer; frequent words quickly merge into single multi-byte subword tokens, so typical English text tokenizes at ~1.3 tokens per word.
- Next connectionHow does BPE decide which pairs of bytes to merge first? We inspect BPE merge frequency tables and the greedy argmax rule.
More context & mechanics
Traditional word-level vocabularies suffer from the Open-Vocabulary Problem:
Vocab V ⊂ Σ^* ⟹ ∃ w ∉ V ⟹ w → \langleUNK⟩
Byte-Level BPE (Radford et al., 2019) seeds the initial vocabulary V₀ with all possible 8-bit byte values:
V₀ = 0x00, 0x01, ṡ, 0xFF , |V₀| = 256
Because any Unicode string S is encoded as a sequence of bytes b = [b₁, ṡ, bₘ] where bᵢ ∈ 0, ṡ, 255:
∀ S ∈ Unicode, b ∈ V₀^*
Every possible text sequence has a valid, non-empty decomposition in V₀.
As BPE merges frequent byte pairs:
V_(k+1) = Vₖ ∪ u ∘ v
The base 256 bytes remain permanently available as fallback tokens, eliminating `<UNK>` completely without sacrificing high-level subword compression.
This byte-level guarantee is implemented in GPT-2, GPT-3, GPT-4, LLaMA-3, and DeepSeek, allowing models to process Python code, binary payloads, Cyrillic, Chinese, and emojis without crashing.
Rico Sennrich et al. introduced BPE to neural MT in 2015. Radford et al. (OpenAI, 2019) adapted it to raw bytes in GPT-2 ('Language Models are Unsupervised Multitask Learners').
- 256 base bytes guarantee that no byte is left behind.
- Any digital string can be spelled in raw bytes; UNK is dead.
How does Byte Pair Encoding iteratively extract and merge the most frequent adjacent token pairs using greedy argmax selection?
Imagine you are editing a manuscript and notice that the letters 't' and 'h' appear together 50,000 times. You create a new custom shortcut stamp 'th' and replace every occurrence of 't' and 'h' with your new stamp. Then you count again: now 'th' and 'e' appear together 40,000 times, so you create a stamp 'the'. BPE is this exact greedy compression loop: count all neighboring pairs, pick the single pair that appears most often, glue them together into a new token, and repeat until your dictionary reaches exactly 50,257 entries.
- $$Count adjacent symbol bigram frequencies across the training corpus and greedily merge pair (u*, v*) = argmax count(u, v) until target vocabulary size is reached.$$
- Learning goalExecute the greedy argmax merge loop of Byte Pair Encoding on a toy corpus and construct the resulting merge priority dictionary.
- Helpful foundationsPriority queues · Neural Machine Translation with Subword Units (Sennrich et al., 2016)
- Common trapAssuming BPE merge order doesn't matter during encoding; merge rules MUST be applied strictly in the exact order they were discovered during training.
- Next connectionWhy did early NLP architectures hit a brick wall when processing long text sequences? We examine the Recurrent Bottleneck in RNNs.
More context & mechanics
BPE training algorithm:
- Initialize Vocabulary:
V = c ∈ corpus characters/bytes
- Represent Corpus: Tokenize corpus as sequence of atomic symbols C = [t₁, t₂, ṡ, t_N].
- Iterative Merge Loop (for k = 1 to K merges):
- Compute bigram frequency table:
f(u, v) = ∑_(i=1)^(N-1) I(tᵢ = u ∧ t_(i+1) = v), ∀ u, v ∈ V
- Greedily extract the argmax pair:
(u^, v^) = argmax_((u, v)) f(u, v)
- Create new merged symbol:
w_(new) = u^ ∘ v^, V arrow V ∪ w_(new)
- Replace all adjacent occurrences of (u^, v^) in corpus C with w_(new).
The loop terminates when |V| = |V_(target)| (e.g. 50,257 in GPT-2, 128,256 in LLaMA-3).
BPE is trained offline on terabytes of raw text using parallel hash tables and priority queues in Rust (Hugging Face `tokenizers`). Once trained, the ordered merge table is serialized into `merges.txt`.
Philip Gage published Byte Pair Encoding in 1994 in 'The C Users Journal' as a fast data compression technique. Rico Sennrich et al. (ACL 2016) repurposed it for NLP.
- Count the pairs; merge the top score.
- Repeat until the vocabulary reaches target size.
What is the mathematical foundation and geometric intuition of Tokenizer Serialization: Storing and Inverting Subwords?
Understand Tokenizer Serialization: Storing and Inverting Subwords visually: How `vocab.json` and `merges.txt` persist the BPE vocabulary across inference runtimes.. Every transformation preserves core structural invariants while mapping coordinate spaces.
- Learning goalMaster the algebraic and geometric derivation of Tokenizer Serialization: Storing and Inverting Subwords.
- Helpful foundationsLinear Algebra Fundamentals · Matrix Transformations · Vector Spaces
- Common trapAssuming Tokenizer Serialization: Storing and Inverting Subwords is merely a computational trick rather than an invariant spatial law.
- Next connectionConnects to upstream spectral theory and downstream tensor operations.
More context & mechanics
An educational systems architecture diagram on natural warm linen (#f5f4e9) with a 1px slate frame.
Top section: Title in bold sans-serif: "Tokenizer Serialization: Storing and Inverting Subwords". Subtitle: "How `vocab.json` and `merges.txt` persist the BPE vocabulary across inference runtimes."
Middle section: Two visual file representation containers side-by-side:
Left File (`merges.txt`): Ordered list of bigram merge rules priority-ranked from 1 to 50,000. Shows: "t h \n e s \n in g \n th e". The encoder reads this sequentially to contract unseen text.
Right File (`vocab.json`): A key-value hash map mapping unique token strings to contiguous integer IDs: "!": 0, ... "Ġthe": 1169, ... "<|endoftext|>":
50256.
Center Arrow: Shows byte-fallback decoding: arbitrary byte values (0 to 255) ensure zero Out-of-Vocabulary (<UNK>) tokens.
Bottom section: Invertibility Card: "D(E(text)) == text ⟹ A production tokenizer must be strictly lossless and deterministic across all UTF-8 byte streams."
Clear code block styling, generous margins, crisp lines.
This principle is foundational across deep learning optimization, high-dimensional representation, and modern LLM architectures.
"Tokenizer Serialization: Storing and Inverting Subwords: Invariance and structure determine stability under spatial and numerical transformations."
How does BPE Merge Frequency Arithmetic: Dynamic Sequence Contraction operate mathematically at scale?
A worked trace across 4 iterations on toy corpus: "low lower newest widest":
- Learning goalMaster the algebraic and geometric derivation of BPE Merge Frequency Arithmetic: Dynamic Sequence Contraction.
- Helpful foundationsFoundations of Build Llm From Scratch · Coordinate Invariance & Geometric Projections · Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI
- Common trapAssuming BPE Merge Frequency Arithmetic: Dynamic Sequence Contraction is an arbitrary computational trick rather than an invariant spatial law.
- Next connectionConnects upstream foundational lemmas to modern high-dimensional computational systems.
More context & mechanics
An educational algorithmic tokenization trace in square 1:1 format on warm cream parchment (#fcf0db) with a sepia frame.
Top section: Title in navy serif: "BPE Merge Frequency: Dynamic Sequence Contraction". Subtitle: "Counting pair frequencies and merging the most frequent byte pair iteratively."
Middle section: A worked trace across 4 iterations on toy corpus: "low lower newest widest":
Initial Byte Stream: ['l','o','w'], ['l','o','w','e','r'], ['n','e','w','e','s','t'], ['w','i','d','e','s','t'].
Frequency Table:
- Pair ('l', 'o') occurs 2 times
- Pair ('o', 'w') occurs 2 times
- Pair ('e', 's') occurs 2 times
- Pair ('s', 't') occurs 2 times
Merge Step 1: Merge top pair ('e', 's') -> new token 'es'.
Sequence contracts from 24 byte characters to 22 tokens.
Merge Step 2: Merge ('es', 't') -> new token 'est'.
Sequence contracts to 20 tokens.
Bottom section: Algorithmic principle: "BPE builds vocabulary greedily from character bytes up to full subwords, compressing sequence length and saving Transformer attention compute (O(L²))."
Clean tabular presentation, distinct color highlighting for merged tokens, clear square layout.
Every transformation preserves structural invariants while mapping coordinate spaces. When operating in high dimensions, numerical precision and computational efficiency require adhering strictly to canonical mathematical laws.
Formal derivation and peer-reviewed analysis:
Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI
"BPE Merge Frequency Arithmetic: Dynamic Sequence Contraction: Invariance, symmetry, and structure govern mathematical truth across continuous and discrete domains."
How does Tokenizer Serialization: Vocabulary JSON & Merge Rules operate mathematically at scale?
Two serialized asset files shown as code cards:
- Learning goalMaster the algebraic and geometric derivation of Tokenizer Serialization: Vocabulary JSON & Merge Rules.
- Helpful foundationsFoundations of Build Llm From Scratch · Coordinate Invariance & Geometric Projections · Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI
- Common trapAssuming Tokenizer Serialization: Vocabulary JSON & Merge Rules is an arbitrary computational trick rather than an invariant spatial law.
- Next connectionConnects upstream foundational lemmas to modern high-dimensional computational systems.
More context & mechanics
A data structure serialization diagram in square 1:1 format on dark slate (#0f172a) with clean borders.
Top section: Title in white sans-serif: "Tokenizer Serialization: Storing and Inverting Subwords". Subtitle in muted cyan: "How vocab.json and merges.txt decouple subword encoding from the model binary."
Middle section: Two serialized asset files shown as code cards:
Left File (vocab.json - Invertible Hash Map):
A bidirectional mapping between string tokens and integer IDs:
"<|endoftext|>": 50256, "The": 464, " world": 995, ...
Shows forward encoding (string -> ID) and backward decoding (ID -> string).
Right File (merges.txt - Ordered Rule List):
Ordered sequence of verified merge pairs:
"t h ==> th"
"th e ==> the"
"w o r l d ==> world"
Show execution rule: Merges must be evaluated strictly in the exact chronological order of their discovery during training!
Bottom section: Systems invariant: "The model architecture never sees text: it operates purely on integers defined by the immutable tokenizer vocabulary."
Clean code syntax highlighting, bidirectional arrows, high contrast dark theme.
Every transformation preserves structural invariants while mapping coordinate spaces. When operating in high dimensions, numerical precision and computational efficiency require adhering strictly to canonical mathematical laws.
Formal derivation and peer-reviewed analysis:
Radford et al. (2019), Language Models are Unsupervised Multitask Learners, OpenAI
"Tokenizer Serialization: Vocabulary JSON & Merge Rules: Invariance, symmetry, and structure govern mathematical truth across continuous and discrete domains."