Prerequisite: None (Foundational). For Embedding-layer strategies, see 05_Embedding.md.
Reading guide: Beginners should focus on Sections 1–3 and 6.
Why can computers understand what you write?
In the grand narrative of modern artificial intelligence, Large Language Models (LLMs) such as GPT-4, Claude 3, and Llama 3 have taken center stage with their remarkable generation and logical reasoning capabilities. However, before these neural networks with hundreds of billions of parameters can process any information, they must first pass through a critical yet often overlooked step — Tokenization. The Tokenizer is the first gateway connecting human natural language to the machine's binary world, transforming continuous text streams into discrete numerical sequences (Token IDs) that computers can compute, analyze, and understand.
Although tokenization may appear to be a simple string preprocessing step on the surface, the underlying mathematical principles, algorithm choices, and engineering implementation details have profound impacts on the final model's performance, inference cost, multilingual support, and even security. Minor differences in tokenization strategy can cause models to produce garbled indentation when processing Python code, digit errors in mathematical operations, or extremely high "Token inflation rates" for certain non-Latin scripts.
This document provides an exhaustive analysis of Tokenizers. We start from the most fundamental text representation concepts, delve into the mathematical principles and differences of the three mainstream algorithms — Byte-Pair Encoding (BPE), WordPiece, and Unigram; we use a standard BPE code implementation as a blueprint, parsing its Python code logic line by line to reveal the microscopic workings of Training and Encoding; and we compare the evolution from GPT-2 to GPT-4 tokenizers, particularly the engineering wisdom behind their Regex pre-tokenization patterns.
Before diving into code and specific algorithms, we must understand why the NLP field ultimately converged on "Subword" tokenization. This is the result of a long trade-off between computational efficiency, vocabulary coverage, and semantic expressiveness.
Early NLP systems, such as those based on Statistical Machine Translation (SMT), often employed word-level tokenization. This approach is the most intuitive: splitting sentences into words using spaces or punctuation as delimiters.
- Mechanism: Split "I love AI." into ["I", "love", "AI", "."].
- Advantage: Preserves semantic integrity of words — each Token corresponds to a well-defined human language concept.
- Flaw — Vocabulary Explosion: Human language has extremely rich morphological variations. In English, the verb "run" has forms like "runs", "running", "ran"; in morphologically rich languages (e.g., Turkish, Finnish), a single root can generate thousands of variants through agglutinative morphemes. Treating each variant as an independent Token would require maintaining a vocabulary of millions, which is computationally unacceptable.
- Out-of-Vocabulary (OOV) Problem: No matter how large the vocabulary, there will always be unseen words (e.g., neologisms like "uninstagrammable" or proper names). In word-level models, these can only be mapped to a generic <UNK> (Unknown) token, causing complete information loss at that position — catastrophic for translation or comprehension tasks.
To completely solve the OOV problem, researchers once turned to character-level tokenization, decomposing text into individual characters.
- Mechanism: Split "love" into ["l", "o", "v", "e"].
- Advantage: Extremely small vocabulary (only needing the alphabet, digits, and symbols, typically 100-1000 range), theoretically eliminating the OOV problem.
-
Flaws — Excessive Sequence Length and Semantic Sparsity:
- Computational Cost: The Self-Attention mechanism in Transformer models has time complexity proportional to the square of sequence length ($O(N^2)$). Character-level tokenization increases sequence length by 5-10x, causing training and inference costs to rise dramatically.
- Semantic Deficiency: Individual characters (e.g., "t") typically carry no independent semantic information. The model must spend many layers and parameters combining characters to recognize "word" concepts, wasting the model's expressive capacity.
Subword Tokenization is the dialectical synthesis of the above two approaches and the current standard for large language models. Its core philosophy: keep common words intact, split rare words into meaningful sub-components (Subword units).
For example, the word "tokenization" might be split into "token" and "ization" by a subword tokenizer.
- "token" is a high-frequency root, preserved as a whole — the model can directly access its semantic embedding.
- "ization" is a common high-frequency suffix, preserved as a whole.
- This mechanism allows the model to efficiently handle common words while generalizing to unseen compound words (e.g., "modernization", "optimization") through root and affix combinations, achieving unlimited vocabulary expressiveness within a finite vocabulary size.
The three dominant subword algorithms are:
- BPE (Byte-Pair Encoding): Frequency-based merge strategy, widely used in GPT series, Llama, RoBERTa.
- WordPiece: Probability (likelihood)-based merge strategy, originating from BERT.
- Unigram: Probability-based pruning strategy (trimming from a large vocabulary), used in SentencePiece (ALBert, T5).
Byte-Pair Encoding was originally proposed as a data compression algorithm by Philip Gage in 1994. Sennrich et al. introduced it to the NLP domain in 2015 to address the rare word problem in neural machine translation. Today, it has become the cornerstone of GPT-series models.
To thoroughly understand BPE, we go beyond theory and use line-by-line code analysis through a reference implementation (based on Karpathy's minbpe logic) to dissect its inner workings.
The BPE training process is essentially an iterative data compression process.
- Initialization: Decompose all text into base units (typically bytes).
- Statistics: Count the frequency of all adjacent unit pairs (Pairs) in the data.
- Merge: Find the most frequent pair (e.g., ('e', 's')), merge it into a new symbol ('es'), and assign a new ID.
- Iterate: Repeat steps 2 and 3 until the target vocabulary size is reached.
We explain the code through three core functional modules: Statistics, Merge, and Training Loop.
This is the most fundamental atomic operation in BPE: scan the current Token sequence and count the occurrences of each adjacent Token pair.
def get_stats(ids):
"""
Input:
ids (list of integers): Current Token ID list.
Output:
counts (dict): Mapping (id1, id2) -> frequency
"""
counts = {}
# zip(ids, ids[1:]) is a Python trick
# zip produces: [(1, 2), (2, 3), (3, 4)]
# These are exactly all the adjacent pairs we need to count
for pair in zip(ids, ids[1:]):
counts[pair] = counts.get(pair, 0) + 1
return countsDeep Analysis and Key Points:
-
Nature of the Input Data: What is
idsinitially? In modern LLMs (e.g., GPT-4), we use Byte-level BPE. This means the initial state ofidsis the UTF-8 encoded byte sequence of the text, ranging from 0-255. For example, the English letterais 97, and the Chinese character 你 is three bytes. This design is critically important because it guarantees the Tokenizer can handle any Unicode string — even Emoji or never-before-seen foreign scripts — since everything is bytes. -
Time Complexity: This function has time complexity
$O(N)$ , where$N$ is the sequence length. During training, each merge requires rescanning the entire corpus, making naive BPE training very slow ($O(N \cdot V)$ , where$V$ is the number of merges). Industrial implementations (e.g., Tiktoken written in Rust) use linked lists or priority queues to optimize the update process, avoiding full scans.
Once we find the most frequent pair (e.g., (101, 115) corresponding to ('e', 's')), we need to replace all occurrences of (101, 115) in the sequence with a new Token ID (e.g., 256).
def merge(ids, pair, idx):
"""
Input:
ids (list): Current Token list
pair (tuple): The pair of Tokens to merge, e.g., (101, 115)
idx (int): The ID assigned to this new Token, e.g., 256
Output:
newids (list): The new list after merging
"""
newids = []
i = 0
while i < len(ids):
# Check if we've hit the pair to merge, without going out of bounds
# Note: i < len(ids) - 1 prevents out-of-bounds when checking ids[i+1]
if i < len(ids) - 1 and ids[i] == pair[0] and ids[i+1] == pair[1]:
newids.append(idx) # Replace with the new ID
i += 2 # Skip the next two elements since they've been merged
else:
newids.append(ids[i]) # Keep as-is
i += 1
return newidsDeep Analysis and Key Points:
- Greedy Strategy: BPE is greedy. Once the most frequent Pair is selected, it replaces all instances globally. This differs from certain dynamic programming algorithms.
- Sequence Shortening: Each merge operation shortens the
idslist. This is the essence of "compression." For large models, shorter sequences mean more context information can fit within the window. - New ID Assignment: The base vocabulary is 0-255. The first merge produces Token ID 256, the second 257, and so on. GPT-4's cl100k_base vocabulary size is approximately 100,277, meaning this merge process was repeated about 100,000 times during training.
Combining the above two functions forms the BPE trainer.
def train(text, vocab_size, verbose=False):
"""
Input:
text (str): Training corpus text
vocab_size (int): Target vocabulary size (e.g., 50257)
"""
assert vocab_size >= 256
num_merges = vocab_size - 256 # Number of merges to perform
# 1. Preprocessing: Convert text to UTF-8 byte stream
text_bytes = text.encode("utf-8")
ids = list(text_bytes) # Initial list, elements range 0-255
merges = {} # Record merge rules: (p0, p1) -> idx
print(f"Original length: {len(ids)}")
for i in range(num_merges):
# 2. Count current frequencies
stats = get_stats(ids)
if not stats:
break # Exit early if no pairs to merge
# 3. Find the most frequent pair
# key=stats.get means sort by dictionary values (frequency)
pair = max(stats, key=stats.get)
# 4. Assign new ID
idx = 256 + i
# 5. Execute merge
ids = merge(ids, pair, idx)
# 6. Record rule
merges[pair] = idx
if verbose:
print(f"Merge {i+1}/{num_merges}: {pair} -> {idx} (count: {stats[pair]})")
return mergesDeep Analysis and Key Points:
- Core Artifact: After training, the most important artifact is not
idsbut themergesdictionary. This dictionary defines the Tokenizer's "knowledge." When we download a pretrained model, thetokenizer.jsonormerges.txtfile stores exactly this dictionary. - Determinism and Tie-breaking: What if two Pairs have the same frequency? Python's
maxfunction returns the first key encountered when values are equal. To ensure Tokenizer reproducibility (Deterministic), industrial implementations typically specify: when frequencies are equal, select by lexicographical order of the Pair's characters. - Vocabulary Size Trade-off:
vocab_sizeis a critical hyperparameter.- Too small: Results in excessively long sequences, slow model inference, and inability to capture long-range dependencies.
- Too large: Causes the Embedding matrix (vocab_size × hidden_dim) parameter count to explode, increasing training burden; and since rare words have very low frequency, their Embeddings may be undertrained.
With trained merges rules, how do we convert new text into Token IDs? This is an error-prone step. A common beginner mistake: finding the most frequent pair in the text during inference. This is wrong. During inference, merges must be applied strictly in the priority order determined during training.
def encode(text, merges):
# 1. Convert to byte stream
ids = list(text.encode("utf-8"))
while len(ids) >= 2:
# Get all adjacent pairs in the current text
stats = get_stats(ids)
# Find the pair that "exists in the merges rule table AND has the smallest ID
# (i.e., was trained earliest)"
# Smaller ID means higher frequency in the training set, thus higher priority
pair_to_merge = None
min_rank = float("inf") # rank is the ID
for pair in stats:
if pair in merges:
rank = merges[pair]
if rank < min_rank:
min_rank = rank
pair_to_merge = pair
# If no pair in the current sequence exists in our rule table, stop
if pair_to_merge is None:
break
# Execute merge
ids = merge(ids, pair_to_merge, min_rank)
return idsDecoding is the inverse of encoding — relatively simple, but with one key detail: handling invalid bytes.
def decode(ids, vocab):
"""
ids: Token ID list
vocab: Mapping {idx: bytes} (derived from base bytes and merges)
"""
# Map all IDs back to byte strings and concatenate
tokens = b"".join(vocab[idx] for idx in ids)
# errors="replace" is the key
text = tokens.decode("utf-8", errors="replace")
return textWhile BPE dominates the GPT series, WordPiece and Unigram are equally important in models like BERT and T5. Understanding their differences is key to grasping the underlying logic of NLP.
WordPiece was developed by Google and is the core of the BERT model. Its overall flow is very similar to BPE (also bottom-up merging), but the criterion for choosing which pair to merge is entirely different.
A distinctive feature of WordPiece is its ## prefix convention: when building the initial vocabulary, all characters except the first character of a word are prefixed with ## to indicate they are continuation pieces. For example, the word tokenization is initially split as ["token", "##ization"] in BERT. This makes it easy to reconstruct original words during decoding — any token starting with ## is simply appended to the previous token.
-
BPE criterion: Select the pair with the highest frequency.
- Goal: Maximize data compression ratio.
-
WordPiece criterion: Select the pair whose merge would increase the training data likelihood the most.
-
This is equivalent to selecting the pair with the highest Pointwise Mutual Information (PMI).
-
WordPiece scoring formula:
$$\text{Score}(A, B) = \frac{P(AB)}{P(A) \times P(B)}$$ where
$P(AB)$ is the probability of pair$AB$ occurring, and$P(A)$ ,$P(B)$ are their individual probabilities.
-
Deep Insight: Why is PMI superior to frequency? WordPiece's scoring mechanism accounts for the independent probabilities of subwords.
- Suppose A="the" and B="book" are both extremely high-frequency words. Their concatenation "thebook" might appear frequently. BPE might merge them.
- In WordPiece, since the denominator
$P(\text{"the"}) \times P(\text{"book"})$ is very large, the Score gets pulled down. This prevents two independently common words from being accidentally merged. - Conversely, suppose A="Z" and B="qa" are both rare, but whenever they appear, they always stick together (e.g., "Zqa"). Then
$P(AB) \approx P(A) \approx P(B)$ , and the Score becomes very high (approaching $1/P(A)$). - Conclusion: WordPiece tends to merge pairs with strong intrinsic association (tighter than random combination), not merely high-frequency pairs. This makes WordPiece generally more linguistically sound than BPE when handling affixes (e.g., "un-", "-ing").
Unigram Tokenization (primarily implemented in the SentencePiece library) takes a fundamentally opposite approach. BPE and WordPiece are bottom-up construction; Unigram is top-down.
Mathematical Principles and EM Algorithm:
The Unigram model assumes each subword occurs independently. The probability of a sentence
where
Training Flow (EM Algorithm):
-
Initialization: Build an extremely large vocabulary (e.g., containing all substrings that appear in the corpus, potentially millions).
-
E-step (Expectation): Fix the current vocabulary and use the Viterbi algorithm to compute the optimal segmentation path for each sentence in the corpus.
- For the word "tokenization", there may be multiple segmentation options (["token", "ization"] vs ["t", "o", "ken", "..."]). The Viterbi algorithm finds the path that maximizes the joint probability
$P(\mathbf{x})$ .
- For the word "tokenization", there may be multiple segmentation options (["token", "ization"] vs ["t", "o", "ken", "..."]). The Viterbi algorithm finds the path that maximizes the joint probability
-
M-step (Maximization): Recompute each subword's occurrence probability
$P(x_i)$ . -
Compute Loss and prune: Calculate how much the total likelihood
$L$ would decrease if a subword$x$ were removed from the vocabulary.$$\Delta L = L_{new} - L_{old}$$ -
Pruning strategy: Remove Tokens that contribute least to total likelihood (typically 20% per round).
-
Loop: Repeat until the vocabulary shrinks to the target size.
Unique Advantage — Subword Regularization:
Unigram is not just a tokenizer — it is itself a miniature language model. During LLM training, we can leverage Unigram's probabilistic nature for data augmentation.
- For the same phrase "New York", we don't always output the optimal segmentation ["New", " York"].
- We can sample according to probability, sometimes segmenting it as ["N", "ew", " Yo", "rk"].
- This technique forces the model to learn semantics under different segmentations, significantly improving robustness to spelling errors and noisy text.
| Property | BPE (GPT-2/3/4, Llama) | WordPiece (BERT) | Unigram (T5, ALBERT) |
|---|---|---|---|
| Build Direction | Bottom-up | Bottom-up | Top-down |
| Core Metric | Frequency | Likelihood Gain / PMI | Likelihood Loss |
| Training Complexity | Lower | High (must recompute all Pair scores each step) | Higher (requires EM iteration) |
| OOV Handling | Byte fallback | Character fallback (needs UNK Token) | Character fallback |
| Tokenization Determinism | Deterministic | Deterministic | Probabilistic (Sampable) |
| Use Cases | Generative models | Understanding models (NLU) | Tasks requiring regularization |
OpenAI's GPT series has consistently used the BPE algorithm, but with critically important optimizations in the details. Understanding this evolution reveals why GPT-4 is so much better than GPT-2 at writing code and handling non-English languages.
The BPE algorithm itself is "blind." Without intervention, it might merge across punctuation and word boundaries. For example, it might merge the "g." in "dog." into a single Token. This is generally undesirable since punctuation typically has independent grammatical meaning.
Therefore, before running BPE merges, a regex is used to split text into basic "word chunks." BPE can only merge within these chunks, not across them.
GPT-2's Regex pattern (Python re syntax):
r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""Segment-by-segment breakdown:
'(?:[sdmt]|ll|ve|re): Handles contractions. Strips 's, 't, 're etc. from words. E.g., "don't" splits into "don" and "'t". This ensures the model understands negation, possessives, etc.?\p{L}+: Handles words. Matches an optional leading space plus a string of letters. Note: GPT-2 treats the space as part of the word (typically at the beginning), liketoken.?\p{N}+: Handles numbers. Matches consecutive digits.?[^\s\p{L}\p{N}]+: Handles punctuation. Matches sequences of non-space, non-letter, non-digit characters.\s+(?!\S): Handles trailing whitespace.
GPT-2's Flaws:
This regex handles multiple spaces poorly and is extremely inefficient with code indentation (which is typically lots of spaces). More importantly, its case handling is imperfect. It can recognize 's as a contraction, but if the user inputs uppercase HOW'S, the 'S might not be split separately due to the lack of a case-insensitive flag, causing inconsistent tokenization.
GPT-4 (and the Tiktoken library) uses a more sophisticated Regex:
r"""(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\r\n\p{L}\p{N}]?\p{L}+|\p{N}{2,}|[^\r\n\p{L}\p{N}]?[^\s\p{L}\p{N}]+[\r\n]*|\s*[\r\n]+|\s+(?!\S)|\s+"""Major Improvements:
- Case-insensitive
(?i:...): Solves GPT-2's inconsistency between "Don't" and "DON'T". Seemingly minor, but dramatically improves the model's understanding of uppercase input. - Number merge strategy
\p{N}{2,}: GPT-4 requires number matches of at least two digits. This tends toward more aggressive number splitting, preventing very long number strings from being merged into extremely rare Tokens that the model can't understand numerically. - Space and code optimization: GPT-4's regex allows merging more consecutive spaces. This is critically important for Python code (which relies on indentation). GPT-2 often splits 4 spaces into 4 Tokens, wasting precious context window, while GPT-4 can compress them into one Token, dramatically improving long code handling.
In GPT-2's source code, bytes_to_unicode is a deceptively confusing but critically important function. It is the foundation that enables the BPE algorithm to handle arbitrary byte streams (including Unicode gibberish, binary files, Emoji, etc.).
BPE operates at the byte level, meaning it must handle all possible values from 0-255. However, this creates a massive engineering problem:
- Invisibility and interference: Many bytes are invisible control characters (e.g., space, newline
\n, tab\t), or even invalid binary data (e.g.,0x00). - Debugging nightmare: If these bytes were used directly as Tokens, printing debug info would cause terminal garbling, misaligned newlines, or even beeping. More importantly, at this stage, the human eye cannot distinguish "empty string" from "space character".
OpenAI didn't filter out these special bytes — instead, they dressed them in a "visible costume." The function builds a reversible mapping table:
- Visible characters stay as-is: Standard ASCII printable characters (e.g.,
a-z,A-Z,0-9,!,?) remain unchanged, mapped directly to their corresponding Unicode characters. - Invisible characters get converted: All invisible characters (spaces, control characters) and non-ASCII bytes are mapped to visible characters in the Unicode Latin Extended region (starting at position 256+).
The Most Classic Mapping: Space
- Original byte: 32 (
0x20) — invisible on screen. - Mapped result:
Ġ(U+0120, Latin Capital Letter G with Dot Above). - Purpose: Makes spaces clearly visible in tokenization results. This is why we always see
Ġworldinstead ofworldin GPT's Token lists.
To appreciate the elegance, recognize that this conversion is not just a "display effect" — it's a substantive data-level change.
| Stage | Data Form | Description |
|---|---|---|
| Step 1: Raw Input | b'Hi world' |
Contains raw bytes, space is 0x20. |
| Step 2: Mapping | "HiĠworld" |
Key step. Byte 0x20 replaced by character Ġ. All subsequent BPE runs entirely on this new string. |
| Step 3: Vocab Storage | {"Ġworld": 12345} |
In vocab.json, Tokens are stored with Ġ literally. Model training also targets Ġ. |
| Step 4: Decode Reversal | b'Hi world' |
Reverse process. When the model outputs Tokens, the Decoder looks up the reverse mapping table, converting Ġ back to byte 0x20. |
| Step 5: Final Display | "Hi world" |
Byte stream decoded via UTF-8, presenting normal text to the user. |
| Model | Vocab Size | Impact |
|---|---|---|
| GPT-2 | 50,257 | Smaller. English-centric, low efficiency for other languages. |
| GPT-4 | 100,277 | Doubled. Significantly improved multilingual compression and code efficiency. |
| Llama 3 | 128,000 | Even larger. Further optimized multilingual support. |
Why are vocabularies getting larger?
A larger vocabulary means the same sentence gets split into fewer Tokens.
- Advantages:
- Faster inference: Fewer generation steps needed.
- "Larger" context: More actual text fits within the same Token limit.
- Multilingual fairness: Larger vocabularies can accommodate more common words from non-English languages (e.g., Chinese characters), reducing "Token inflation" for non-English text.
- Cost: Embedding layer parameter count explodes (a 128k × 4096-dim matrix is enormous), training convergence becomes harder, and more data is needed to fill these sparse Token embeddings.
In code implementations, special Tokens (e.g., <|endoftext|>, <PAD>, <MASK>, <|im_start|>) are often the most confusing part for beginners, and a common source of model hallucinations or security vulnerabilities.
Suppose our special Token is <|endoftext|>, used to mark the end of text. If we pass it to the BPE algorithm as regular text:
- BPE would first split it by characters.
- Then following merge rules, it might be split into
['<', '|', 'endo', 'ft', 'ext', '|', '>']. - Consequence: The model cannot recognize this sequence as a unified "stop signal" — just meaningless fragments. The model may fail to stop generating properly.
Tiktoken (GPT-4) approach:
Tiktoken requires users to explicitly pass the allowed_special parameter. This is for security.
- Prompt injection defense: If special Tokens are disallowed, when a user inputs "Hello <|endoftext|>", Tiktoken will forcibly tokenize it as regular text (i.e., split it up), preventing users from forging system instructions.
- Implementation: Tiktoken internally maintains a separate dictionary for special Tokens. Before tokenization begins, it uses regex to "extract" these special strings, excluding them from BPE merging and directly assigning specific IDs.
HuggingFace Tokenizers approach:
HF introduces AddedToken objects and distinguishes between special_tokens (with special semantics, like EOS) and additional_special_tokens. HF's tokenization pipeline includes a Normalization step, but when handling special Tokens, it similarly protects them from being split.
The Tokenizer is not just a data porter — it actually reshapes how the model sees the world. Many bizarre LLM behaviors can be traced back to the tokenization stage.
LLMs typically struggle with arithmetic tasks, partly due to tokenization.
- Inconsistency:
1000might be one Token.1001might be split into ["100", "1"].1002might be ["10", "02"]. - Place Value Loss: Because numbers are split irregularly and inconsistently, the model struggles to learn unified "Place Value" rules (i.e., the relationship between ones, tens, hundreds places).
- GPT-4's Improvement: Restricts number merging via regex to maintain consistency in number segmentation, but this remains an inherent limitation of text-based models.
In Python code, indentation is logic.
- In GPT-2's Tokenizer, 4 spaces are typically split into 4
ĠTokens. This means deeply indented code consumes a huge Token quota, and the model must precisely count how manyĠthere are to determine code block nesting level. - GPT-4 significantly alleviated this problem by merging consecutive spaces, making the model's code generation more logically rigorous and improving context utilization.
Researchers discovered that certain Tokens (e.g., SolidGoldMagikarp, Dragonbound) cause models to generate gibberish or crash.
- Cause: These words typically come from Reddit usernames that were counted as high-frequency words during data crawling and added to the vocabulary.
- Disaster: However, during subsequent training data cleaning, these words may have been filtered out as "noise."
- Result: These Tokens exist in the vocabulary but were never updated during Embedding layer training (remaining in their initial random state). When the model encounters these words during inference, it activates an untrained random vector, causing output to break down. This reminds us that data preprocessing and postprocessing must be strictly aligned when building Tokenizers.
Fertility is a key metric for measuring the coupling efficiency between a Tokenizer and the Embedding space.
- Definition: The ratio of Tokens generated per word or character.
- Efficiency Impact: Lower Fertility means each Token carries more information, improving inference speed and reducing VRAM usage.
- Multilingual Challenge: English-centric tokenizers tend to produce extremely high Fertility for Asian languages (e.g., Thai, Chinese), degrading efficiency for models like Llama when processing these languages. For deeper optimization strategies on the Embedding layer, please refer to the dedicated document.
In engineering practice, we rarely run pure-Python BPE directly due to low efficiency. We typically use highly optimized libraries.
| Library | Core Language | Algorithms | Features | Models |
|---|---|---|---|---|
| Tiktoken (OpenAI) | Rust | BPE | Blazing fast (3-6x faster than HF). Optimized for OpenAI models. Simple API, inference only. | GPT-3.5, GPT-4 |
| SentencePiece (Google) | C++ | BPE, Unigram | Lossless processing. Treats spaces as special character ▁, no pre-tokenization regex needed. Fully reversible. Excellent multilingual support. |
Llama, ALBERT, T5 |
| Tokenizers (HuggingFace) | Rust | All | Unified. Most feature-complete, supports both training and inference. Integrates advantages of both above, but more complex API. | BERT, RoBERTa, Mistral |
A key motivation for SentencePiece is that BPE, WordPiece, and Unigram all assume the input text uses spaces to separate words. This assumption breaks down for languages without clear word boundaries, such as Chinese, Japanese, Korean, and Arabic. While language-specific pre-tokenizers exist, they are not generalizable. SentencePiece solves this by treating the entire input as a raw byte stream — including spaces — and then applying BPE or Unigram directly on it.
Traditional Tokenizers (like BERT) split by spaces first, losing the information of "how many spaces were originally here." SentencePiece treats spaces as ordinary characters (represented by underscore ▁ or U+2581).
- Input:
Hello World(two spaces) - SP tokenization:
["▁Hello", "▁", "World"](all information preserved) - This is why models like Llama can directly process raw text without complex preprocessing rules. This "Raw stream in, Token stream out" design philosophy is the mainstream for current open-source large models.
Tokenization is an ancient yet vibrant field in NLP. From early space-splitting, to statistical BPE, to today's complex systems fusing linguistic rules with probabilistic graphical models, every evolution of the Tokenizer has pushed the boundaries of model performance.
Where is the future heading?
- Token-free Models (Byte-level Transformers): Researchers are exploring training directly at the byte level (MegaByte, MambaByte). Although sequence length increases 4x, with developments like Flash Attention and linear attention mechanisms, this is becoming feasible. This would completely eliminate all biases and problems introduced by Tokenizers.
- Multimodal Fusion: With models like GPT-4o, Tokenizers must handle not just text, but also image patches and audio frames. Future Tokenizers will be unified "everything is a Token" systems.
By understanding every byte, every line of code, and every regex symbol in a Tokenizer, we are not just learning a preprocessing tool — we are glimpsing the "first look" through which large language models perceive the world. That first look determines how far they can see.
A complete BPE tokenizer training script using the HuggingFace Tokenizers library, configured for Transformers compatibility.
"""
Tokenizer Training Script
This script trains a BPE (Byte Pair Encoding) tokenizer from a JSONL-format
pretraining dataset, configured to be compatible with HuggingFace Transformers
standard format.
Main features:
1. Read text data from JSONL dataset
2. Train tokenizer using BPE algorithm with vocab size of 6400
3. Define and configure special Tokens (<|endoftext|>, <|im_start|>, <|im_end|>)
4. Save tokenizer in HuggingFace-compatible format
5. Configure chat_template for multi-turn conversation formatting
"""
import random
import json
from tokenizers import Tokenizer, models, trainers, pre_tokenizers, decoders
import os
from transformers import AutoTokenizer
# Set random seed for reproducibility
random.seed(42)
def train_tokenizer():
"""
Train a BPE tokenizer from a JSONL dataset, define special Tokens, save in standard format.
"""
# ========== Step 1: Read JSONL Dataset ==========
def read_texts_from_jsonl(file_path):
with open(file_path, 'r', encoding='utf-8') as f:
for line in f:
data = json.loads(line)
yield data['text']
# Pretraining data path
data_path = './dataset/pretrain_hq.jsonl'
# ========== Step 2: Initialize BPE Tokenizer ==========
tokenizer = Tokenizer(models.BPE())
tokenizer.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=False)
# ========== Step 3: Define Special Tokens ==========
# Note: The order of these Tokens is critical! The trainer assigns IDs (0, 1, 2) in this order
special_tokens = ["<|endoftext|>", "<|im_start|>", "<|im_end|>"]
# ========== Step 4: Configure BPE Trainer ==========
trainer = trainers.BpeTrainer(
vocab_size=6400,
show_progress=True,
special_tokens=special_tokens,
initial_alphabet=pre_tokenizers.ByteLevel.alphabet()
)
# ========== Step 5: Train Tokenizer ==========
texts = read_texts_from_jsonl(data_path)
tokenizer.train_from_iterator(texts, trainer=trainer)
# ========== Step 6: Set Decoder and Verify Special Tokens ==========
tokenizer.decoder = decoders.ByteLevel()
assert tokenizer.token_to_id("<|endoftext|>") == 0
assert tokenizer.token_to_id("<|im_start|>") == 1
assert tokenizer.token_to_id("<|im_end|>") == 2
# ========== Step 7: Save Tokenizer ==========
tokenizer_dir = './model/'
os.makedirs(tokenizer_dir, exist_ok=True)
tokenizer.save(os.path.join(tokenizer_dir, "tokenizer.json"))
tokenizer.model.save("./model/")
# ========== Manually Create tokenizer_config.json ==========
config = {
"add_bos_token": False,
"add_eos_token": False,
"add_prefix_space": False,
"added_tokens_decoder": {
"0": {
"content": "<|endoftext|>",
"lstrip": False,
"normalized": False,
"rstrip": False,
"single_word": False,
"special": True
},
"1": {
"content": "<|im_start|>",
"lstrip": False,
"normalized": False,
"rstrip": False,
"single_word": False,
"special": True
},
"2": {
"content": "<|im_end|>",
"lstrip": False,
"normalized": False,
"rstrip": False,
"single_word": False,
"special": True
}
},
"bos_token": "<|im_start|>",
"eos_token": "<|im_end|>",
"pad_token": "<|endoftext|>",
"unk_token": "<|endoftext|>",
"tokenizer_class": "PreTrainedTokenizerFast",
"model_max_length": 32768,
}
with open(os.path.join(tokenizer_dir, "tokenizer_config.json"), "w", encoding="utf-8") as config_file:
json.dump(config, config_file, ensure_ascii=False, indent=4)
print("Tokenizer training completed and saved.")
def eval_tokenizer():
"""
Verify core tokenizer functionality.
"""
tokenizer = AutoTokenizer.from_pretrained("./model/")
messages = [
{"role": "system", "content": "You are an excellent chatbot that always gives correct responses!"},
{"role": "user", "content": "Where are you from?"},
{"role": "assistant", "content": "I come from Earth."}
]
new_prompt = tokenizer.apply_chat_template(
messages,
tokenize=False
)
print(new_prompt)
actual_vocab_size = len(tokenizer)
print('Actual vocab size:', actual_vocab_size)
model_inputs = tokenizer(new_prompt)
print('Encoded length:', len(model_inputs['input_ids']))
input_ids = model_inputs['input_ids']
response = tokenizer.decode(input_ids, skip_special_tokens=False)
print('Decoded matches original:', response == new_prompt)
def main():
train_tokenizer()
eval_tokenizer()
if __name__ == "__main__":
main()- Gage (1994): A New Algorithm for Data Compression (Original BPE).
- Sennrich et al. (2016): Neural Machine Translation of Rare Words with Subword Units (BPE for NLP).
- Kudo & Richardson (2018): SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing.
- Kudo (2018): Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (Unigram).
- Radford et al. (2019): Language Models are Unsupervised Multitask Learners (GPT-2 byte-level BPE).
- OpenAI (2023): Tiktoken — fast BPE tokenizer in Rust.