Bite Pair Encoding (BPE) Tokenizer

Bite Pair Encoding (BPE) Tokenizer

• BPE is a tokenization scheme behind modern LLMs like GPT-2, GPT-3, and the original ChatGPT.
• Tokenization algorithms can be word-based, subword-based, or character-based.

Word-Based Tokenization

• In word-based tokenization, each word in a sentence is a token.
• Example: "The fox chased the dog" becomes tokens: "the", "fox", "chased", "the", "dog".
• Difficulty handling out-of-vocabulary (OOV) words is a problem.
• OOV words are those not present in the training vocabulary, leading to potential errors.
• Another problem is the inability to capture similarities between words like "boy" and "boys."
• Similarity is not captured as "boy" and "boys" are treated as separate individual tokens.

Character-Based Tokenization

• In character-based tokenization, each character is a token.
• Example: "My hobby is playing cricket" becomes tokens: "m", "y", "h", "o", "b", "b", "y", etc.
• Advantage of character-based tokenization is a small vocabulary size due to a limited number of characters.
• The English language has 256 characters, much less than the 170,000-200,000 words.
• It solves the OOV problem, as any new sentence can be broken down into known characters.
• Disadvantage is the loss of meaning associated with words.
• The tokenized sequence becomes much longer than the raw text.
• Example: "dinosaur" becomes 8 tokens: "d", "i", "n", "o", "s", "a", "u", "r".

Subword-Based Tokenization

• Subword-based tokenization aims to combine the advantages of word-based and character-based approaches.
• Frequently used words are not split into smaller subwords.
• Rare words are split into smaller, meaningful subwords, even to the character level if needed.
• Example: "boy" (frequent) remains as a token, while "boys" (less frequent) is split into "boy" and "s."
• Subword splitting helps the model learn that different words with the root word are similar in meaning.
• Example: "token", "tokens", and "tokenizing" share the "token" root.
• It also helps the model learn common suffixes, such as "ization" in "tokenization" and "modernization".

Bite Pair Encoding (BPE) as Subword Tokenization

• BPE is a subword tokenization algorithm used in modern LLMs.
• BPE was initially introduced in 1994 as a data compression algorithm.
• It identifies the most common pair of consecutive bytes in data and replaces them with a byte that doesn't occur in the data.
• This process is done iteratively.
• Example: In the data "AABAABAC," the most common pair "AA" is replaced by "Z" (not in data), resulting in compressed data.

BPE in Large Language Models

• BPE for LLMs ensures that common words are represented as a single token.
• Rare words are broken down into two or more subword tokens.
• All tokens are augmented with an end token().
• Example: In a dataset with "old", "older", "finest", and "lowest," each word will have a "" ending.
• The words are then divided into characters and frequency table is constructed.
• The most frequent pairings are merged.

BPE Algorithm Steps Illustrated

• Start with data set of words with added end token ().
• Split all words into individual characters.
• Make a frequency table.
• The most frequent byte pairing is identified.
• The identified most frequent pairing is merged.
• The process is repeated.
• This identifies common roots, like "old" in "old" and "older," that word-based and character-based methods miss.
• Algorithm is stopped when enough tokens have been created or the iterations have stopped

Advantages of BPE

• BPE solves the OOV problem.
• BPE provides a manageable size vocabulary.
• By retaining the root words meanings (such as EST and old), it also solves the problem of the word level encoding.

Tick Token Library

• Tick Token is a Python open-source library using Bite Pair Encoder for OpenAI models.
• It can be used to instantiate the bite pair encoding tokenizer.
• The tokenizer object has encode and decode methods.
• encode method converts words into token IDs.
• decode method decodes token IDs back into words.
• Example sentence: "Hello, do you like T? In the sunlight terraces of some unknown place".
• End of text-token separates entire documents for the model.

Observations on Tick Token

• The `` token is assigned to a large token ID, 50256.
• The GPT-2's BPE tokenizer has a vocabulary size of 50257.
• BPE tokenizer encodes and decodes unknown words by breaking them into subword units or characters.
• The tokenizer scans from left to right, breaking words into subwords/characters, then assigns IDs.