1.1 Tokenization

1.1 Tokenization

1.1.1 Introduction

Why tokenization?

Three Levels of Tokenization

1. Word-Level Tokenization
• In English, words are split by spaces. In Chinese, tools like Jieba can be used for tokenization.
• Advantages:
• Preserves word boundaries and meanings.
• Disadvantages:
• Long-Tail Effect: The vocabulary can be extremely large, including many rare words, making storage and training costly. Rare words are also difficult to learn well.
• OOV (Out of Vocabulary) Issue: Words not in the vocabulary cannot be processed.
• Lack of Handling for Morphological and Inflectional Relationships: Different forms of the same word (e.g., inflections, synonyms) are treated as completely separate words, increasing training costs and failing to capture relationships between words. It also prevents learning Inflectional similarities across different words.

2. Character-Level Tokenization
• Addresses the OOV issue by breaking words down into individual characters.
• Advantages:
• Small vocabulary size. For example, in English, 26 letters lead to all words; in Chinese, around 5,000 characters can form most words, requiring only a few extra special characters.
• Disadvantages:
• Cannot capture rich semantic meanings of words.
• Increased sequence length, leading to higher computational costs.

3. Subword-Level Tokenization
• Falls between character-level and word-level tokenization. The idea is to preserve frequently occurring words while breaking down rare words into subword units for compression.
• Advantages:
• Provides a balance between vocabulary size and expressive power
• OOV issues can be mitigated by combining subword units.
• Main Subword Tokenization Algorithms:
• BPE (Byte Pair Encoding)
• WordPiece
• Unigram Language Model

Examples

Problems

1.1.2 Tokenization Algorithms

Byte Pair Encoding (BPE)

• Core Idea: Start with a basic vocabulary and continuously merge the most frequent adjacent token pairs to generate new tokens.

• Details: Input training corpus and set the desired vocabulary size V.
a. Prepare initial vocabulary: Include 26 English letters and various symbols, initializing them with unique IDs.
b. Segment words in the corpus based on the initial vocabulary into the smallest units.
c. Count the frequency of adjacent unit pairs in the corpus and merge the most frequent pair.
d. Repeat steps until reaching the predefined subword vocabulary size or until the next merge has a frequency of 1.

• Advantages:
• Effectively balances vocabulary size and granularity (trades off token count and vocabulary size).

• Disadvantages:
• Due to the greedy and deterministic process, it does not provide multiple tokenization results with probabilities (relative to ULM).
• Decoding ambiguity issues: The output segmentation may not be as expected (e.g., for the sentence "Hello World", results might be "Hell/o/world" or "He/llo/world").

• BPE Example
a. Prepare training corpus: Prepare a simple training corpus in the form of [frequency] word_, where _ denotes the word ending. This example includes five words and their frequencies.
Note: er_ and er have different meanings; er_ can only appear at the end of a word, such as newer_; er does not indicate a suffix but can form era, etc.

Frequency	Word
[5]	low_
[2]	lowest_
[6]	newer_
[3]	wider_
[2]	new_

b. Set the desired size of the token vocabulary or looping times as a termination condition
c. Count the occurrences of each character, including the number of times "_" appears. This table will serve as the vocabulary, which will be used for tokenization after the subsequent iterations are completed.

Character	Frequency
_	18
d	3
e	19
i	3
l	7
n	8
o	7
r	9
s	2
t	2
w	22

d. Select two consecutive characters (in sequence) to merge, choosing the pair with the highest frequency. In the first iteration, select r and _, merging them into r_, which appears 6 + 3 = 9 times in total. Then, add r_ and its frequency to the vocabulary while subtracting the frequencies of r and _. At this point, the frequency of r becomes 0, meaning that r always appears in association with _ and that r is always the last character of a word. Therefore, r can be removed from the vocabulary. Since one new token r_ is added and one token r is removed, the vocabulary size remains unchanged. (This explains why vocabulary size generally increases before decreasing during the process.)

Character	Frequency
_	9
d	3
e	19
i	3
l	7
n	8
o	7
r	0
s	2
t	2
w	22
r_	9

e. Next, merge e and r_, as er_ appears 6 + 3 = 9 times, making it the most frequent pair. Similarly, update the vocabulary:
• Add er_ and its frequency.
• Remove r_, as its frequency becomes 0.
Since one token er_ is added and one r_ is removed, the vocabulary size remains unchanged.

Character	Frequency
_	9
d	3
e	10
i	3
l	7
n	8
o	7
s	2
t	2
w	22
er_	9
r_	0

f. Then, merge e and w, which appear 8 times in total. After updating the vocabulary becomes (_, d, e, i, l, n, o, s, t, w, er_, ew). Since ew does not eliminate all occurrences of e or w (e.g., in "wider," e and w remain separate), the vocabulary size increases by 1.
g. Next, merge n and ew, which appear 8 times in total. The updated vocabulary becomes (_, d, e, i, l, o, s, t, w, er_, new). Since new completely replaces n and ew, both are removed. The vocabulary size decreases by 1 because one token new was added while two (n and ew) were removed.
h. Let say the iteration stops after four cycles, the final vocabulary is: (_, d, e, i, l, o, s, t, w, er_, new)
i. Vocabulary size changes in three possible ways: +1 (When merging does not completely remove both characters, like ew); -1 (When merging eliminates two tokens but adds one, like new); No change (When one token is added and one is removed, like er_)

• BPE code:
There are mainly two functions: one is dedicated to counting vocabulary, and the other is responsible for merging strings. Counting word frequency is very brute-force, that is, traversing each element in the vocabulary, using a sliding window like two elements, combining them one by one, and recording the frequency. After finding the one with the highest frequency, merge it and output a new vocabulary.
• Count vocabulary
• Count adjacent letter pairs frequency
• Combine pairs with highest frequency
• Visualize the tokenization

Byte-level BPE (BBPE)

• Key Idea: Extending BPE (Byte Pair Encoding) to the byte level. This approach ensures that rare characters from noisy text or languages with rich character sets (such as Japanese and Chinese) do not unnecessarily occupy space in the vocabulary, while still maintaining compactness.

• Implementation Details: Uses a 256-character set based on UTF-8 encoding.

• Advantages
1. Comparable efficiency to BPE, but with a significantly reduced vocabulary size.
2. Facilitates better sharing across multiple languages via subwords at the byte level.
3. Ensures good generalization across datasets, even when vocabulary sets do not overlap, by leveraging shared byte-level representations.
4. Achieves effective compression by dynamically generating word representations based on text redundancy and common fragments—particularly useful for handling text with many repeated segments.
5. Versatile across different data types, including text, image data, and other encoding formats, since it operates on byte-level encoding.
6. Lossless compression, unlike statistical compression methods, ensuring that no information is lost in the process.
7. Easier interpretability, since BBPE dynamically generates subword vocabulary from text data, making it simpler to decode compressed text back to its original form.
8. Flexibility, allowing compression rates and vocabulary sizes to be adjusted dynamically to fit various application scenarios.

• Disadvantages
1. Longer encoding sequences – representing text at the byte level may lead to longer sequences than BPE, resulting in higher computational costs.
2. Challenges in byte-level decoding – decoding may require the use of contextual information and dynamic planning algorithms to ensure well-formed sentence outputs.

Note that, the UTF-8 itself is prefix mutually exclusive, which lead to uniqueness during encoding and decoding. However, the tokenization algorithm may learn invalid composition of bytes and lead to invalid generation and decoding of LLMs. Fortunately, this paper mentioned that this invalidness rarely happens in practical, so the GPT-2 tokenizer implementation does not directly support dynamic planning algorithms for tackling this.

• Comparison with BPE
BBPE generates longer byte-level tokens compared to BPE.

Note that Unicode is represented as U+0000 to U+10FFFF to represent all characters on the internet (over a million characters), and usually written as \u0000 to \uFFFF in Python and \U for higher code points. Unicode covers all ASCII characters. Unicode Transformation Format - 8-bit (UTF-8) covers all Unicode characters and encodes code points using variable-width encoding of one to four bytes.

For example, in above, the word proof is represented using UTF-8 as: p → 70, r → 72, o → 6F, f → 66, and their corresponding Unicode is actually: U+0070 , U+0072 , U+006F , U+0066 , respectively. And the so-called underscores are actually LOWER ONE EIGHTH BLOCK and represented as U+2581 in Unicode and E2 96 81 in UTF-8.

• BBPE Code

• The bytes_to_unicode function in the above code basically replaces some symbols in the extended ASCII table (0-255) with other symbols in Unicode. The replaced symbols in the ASCII table are indexed: 0 - 32, 127 - 160, and 173., which exactly correspond to all control characters in Unicode as shown below.





Some references of Unicode standard: https://www.unicode.org/charts/ https://www.unicode.org/charts/PDF/U0000.pdf https://www.unicode.org/charts/PDF/U0080.pdf https://www.unicode.org/charts/PDF/U0100.pdf

• Overall workflow
• Transform text to UTF-8 encodings
• Substitute all bytes to the modified Unicode
• Apply BPE (the vocab starts with the modified Unicode with 256 symbols instead of 26 letters as in BPE)

WordPiece

• Core Idea: Similar to BPE, this method starts with a small vocabulary and continuously merges subwords to generate the final vocabulary. The main difference is that BPE selects token pairs to merge based on frequency, while WordPiece merges tokens based on mutual information between tokens.

• Steps: Given training data and an initial vocabulary size V:
1. Prepare an initial vocabulary: For example, 26 letters and various symbols.
2. Segment the training corpus based on the initial vocabulary to get the smallest possible subwords.
3. Train a language model on the segmented corpus, using, for example, a unigram language model (just frequency), and estimate probabilities via maximum likelihood.
4. From all possible token pairs, choose the one whose merging maximally increases the training data likelihood and merge them. Suppose a sentence consists of a sequence of subwords, , then the likelihood of the sentence is the product of all subword probabilities:
Assume each subword is independent. If we merge two adjacent subwords and into a new subword , the sentence likelihood changes equal the mutual information between and :
In practice, the two subwords with the highest mutual information are selected each time for merging. The probability represents the frequency of occurrence in the corpus. To compute the score, we do not take the log:
5. Repeat step d until reaching the predefined vocabulary size or the likelihood increase being lower than some predefined threshold.

• Advantages: Better trade-off between vocabulary size and OOV (out-of-vocabulary) issues.

• Disadvantages:
• Some unreasonable subword merging results may appear.
• Very sensitive to wrong spelling in the training corpus.
• Not good enough for prefixes.

• Solution: Splitting compound words and prefixes to smooth out probability estimates.

• WordPiece Code
The main difference is the calculation of the score. BPE calculates freq, while WordPiece calculates the score as formulated above.

Unigram Language Modeling (ULM)

• Core Idea: Start with a large vocabulary, then use a unigram language model to compute the loss caused by deleting different subwords. The importance of a subword is represented by this loss: subwords with higher loss values or greater significance are retained. The ULM tends to keep subwords that appear more frequently in tokenization results, because if these subwords are removed, the loss would be significant.

• Link: https://huggingface.co/learn/nlp-course/en/chapter6/7

• Implementation Steps: Input training corpus and initial vocabulary size V
1. Prepare the base vocabulary: Initialize a very large vocabulary, such as all characters + high-frequency n-grams. The vocabulary can also be initialized using the Byte Pair Encoding (BPE) algorithm.
2. Optimize the vocabulary: Use a unigram language model (unigram LM) to estimate the probability of each subword in the corpus (Estimate step). Use the Viterbi algorithm to find the optimal tokenization and calculate word probability.
3. Calculate the overall loss (sum of weighted negative-log probability for words) for the corpus as the baseline, then calculate the new losses by removing each subword. This difference represents the importance of that subword.
4. Sort subwords by loss and remove the subwords with the lowest losses, where lower losses indicate less importance (Maximization step). Ensure that single characters are not removed to avoid excessive Out-of-Vocabulary (OOV) cases.
5. Repeat the process iteratively until the vocabulary size is reduced to the predefined limit.

• Advantages:
• The training algorithm can leverage all possible tokenization results via the Viterbi algorithm.
• This method introduces a tokenization approach based on a language model rather than strict rules, providing a likelihood for multiple tokenization results and helping the model learn the underlying noise in the data.

• Disadvantages:
• Initialization affects performance – A good initial vocabulary, such as one generated via BPE, is beneficial.
• Slightly complex – The iterative pruning process requires multiple steps (EM algorithm) and the Viterbi algorithm (implemented via dynamic programming) to find the best tokenization results.

• ULM Tokenization Example
Note: A token cannot be removed if it exists as a single-character token (e.g., a, b, c) so any word should have at least one valid segmentation (e.g., apple can be tokenized as a, p, p, l, e). ULM uses the Viterbi algorithm to find the most probable tokenization.
1. Vocabulary initialization: Start with the corpus and the frequency of word occurrences to construct the vocabulary. The vocabulary should cover all essential tokens, including all single characters. Ensure that the vocabulary covers the entire corpus; otherwise, the probability calculations will fail in later steps.

2. Select the tokenization with the greatest likelihood: Take hug as an example. The tokenization for hug could: h, u, g, hu, g, h, ug, hug. The first 3 are all covered in the vocabulary, but the fourth hug is not. The maximum probability for this word can be calculated to be



Scores for all words in the corpus are calculated as follows, and then a weighted sum is made. Therefore, the initial value of the Loss is 170.40



3. Reduce the vocabulary: From the results in the image above, we can see that the token ug is not used. The key principle is to remove tokens that have the least impact on Loss. So first, remove the token ug from the vocab. Based on the word splits in the above image, the Loss will not change if token ug is removed (actually, removal of any one of hu, pu, lu, bu, du will not affect the Loss). For example, hug can be expressed as h, ug if hu is removed. Here we just remove ug.



When this token ug is removed, the probabilities calculation for all tokens is changed, as shown above right. Then, we apply the second round of token removal, as shown below. Note that the Loss here is not like training loss when you train a deep learning model: the Loss here represents the importance of a subword; the higher the Loss, the more important the subword is. For example, when you delete a subword that is completely not used, the Loss on the corpus will remain unchanged; when you delete a useful subword that is frequently used, then some words’ likelihood will decrease and the Loss will increase, indicating more importance. So here we remove the bu that has the lowest Loss/importance.



You may notice that: why the Loss for removing bu is neither increasing nor remaining unchanged? This usually means we are already deleting useful subwords, and we should stop.

• ULM Tokenization Code
In this example, you will find that we are always removing tokens that lead to unchanged Loss.

1.1.3 Commonly Used Libraries

SentencePiece

• Multi-granularity segmentation: Supports complete and high-performance BPE, ULM tokenization algorithms, as well as character and word-level tokenization.

• Multilingual support: Uses Unicode encoding for characters, converting all input (English, Chinese, and other languages) into Unicode characters. This resolves issues related to different encoding methods for multiple languages.

• Reversible encoding and decoding: Previously mentioned tokenization algorithms often handled spaces in a crude manner, sometimes making it impossible to recover the original text. SentencePiece explicitly treats spaces as a fundamental symbol using a special character "_" (U+2581) to represent spaces. This enables simple and reversible encoding and decoding. (Reversible encoding and decoding: Decode(Encode(Normalized(text))) = Normalized(text))

• No need for pre-tokenization: SentencePiece can be trained directly on raw text/sentences without requiring pre-tokenization.

• Fast and lightweight.

Tokenizers

• Normalization: Cleaning, removing spaces, removing diacritics, converting to lowercase, Unicode normalization

• Pre-tokenization: Breaking text into smaller objects, representing the upper bound of the token number at the end of training. A useful approach is to pre-segment the text into "words," so the final tokens are parts of these words. For example, splitting by spaces and outputting a list where each element is a token.

• Model: Specific tokenization algorithm, e.g., tokenizer = Tokenizer(BPE(unk_token="[UNK]"))

• Post-processing: Post-processing steps such as adding special tokens like [CLS], [SEP], etc.

1.1.4 Comparison

• Comparison between WordPiece and BPE: Both follow a merging approach, breaking text into the smallest units (e.g., 26 English letters with various symbols as an initial vocabulary) and then merging them. The vocabulary grows from small to large. The key difference is that WordPiece merges based on mutual information between tokens, while BPE merges based on token-pair occurrence frequency.

• Comparison between WordPiece and ULM: Both use language models to select subwords. The difference lies in the vocabulary growth: WordPiece starts with a small vocabulary and grows larger, while ULM starts with a large vocabulary and removes words based on probability until certain constraints are met. The ULM algorithm considers multiple possibilities in a sentence, allowing it to output multiple tokenization results with probabilities.