LLM [3] Tokenizer
- 01LLM [1] Data, hardware, and the model choice
- 02LLM [2] Preparing the data
- 03LLM [3] Tokenizer
3. Tokenizer
So we have text. But a neural network works with numbers. That means we need to assign a number to every word. Take a dictionary of English words, give each word a number - and we almost have a tokenizer. What is left is deciding which numbers to give to punctuation, digits, articles, made-up words and parts of words. In essence, a token is the id of a word. And a word is not always a dictionary word. Sometimes it is a model name made of letters, symbols and digits.
BPE (Byte-pair encoding) was invented to tokenize words. Early versions used an <|unk|> token for words missing from the vocabulary. Modern BPE does not need <|unk|> - it can encode any combination of letters and symbols. To do that, it splits a word into word pieces. The smallest unit is one byte. That is why it can break any made-up word into tokens.
The only special token in the base tiktoken tokenizer, which we are going to use, is <|endoftext|>. But we can always add our own tokens. That makes sense if we train our model to perform certain actions, for example to call a program function. Then the appearance of such a token in the generated text means the LLM intends to call that function, and once we see the token in the output, we should call the function.
Here is an example of the simplest tokenizer. We will not use it. It is here only to understand the principle. This is what it does:
- Splits the input text into words, and the words into characters. The tiktoken library, which we use later, does the same, but splits words into UTF-8 bytes instead of characters. That is why it does not need
<|unk|>: any text is made of the 256 possible bytes. - Repeatedly merges adjacent token pairs if the pair is among the merges learned during training. This simplified version walks through a word from left to right and merges the first matching pair. Real BPE (and tiktoken) first applies the pair that was learned earliest, i.e. the one with the highest rank. That is why below
" and"fell apart into" a","n","d", even though it is one of the most frequent words. - Keeps merging until there is no pair left that could be merged.
- The result is a list of token ids.
Code for this post: gpt/tokenizer
from collections import Counter, deque
from functools import lru_cache
import yaml
class BPETokenizerSimple:
def __init__(self):
# Maps token_id to token_str (e.g., {11246: "some"})
self.vocab = {}
# Maps token_str to token_id (e.g., {"some": 11246})
self.inverse_vocab = {}
# Dictionary of BPE merges: {(token_id1, token_id2): merged_token_id}
self.bpe_merges = {}
def train(self, text, vocab_size, allowed_special={"<|endoftext|>"}):
"""
Train the BPE tokenizer from scratch.
Args:
text (str): The training text.
vocab_size (int): The desired vocabulary size.
allowed_special (set): A set of special tokens to include.
"""
# Preprocess: Replace spaces with 'Ġ'
# Note that Ġ is a particularity of the GPT-2 BPE implementation
# E.g., "Hello world" might be tokenized as ["Hello", "Ġworld"]
# (GPT-4 BPE would tokenize it as ["Hello", " world"])
processed_text = []
for i, char in enumerate(text):
if char == " " and i != 0:
processed_text.append("Ġ")
if char != " ":
processed_text.append(char)
processed_text = "".join(processed_text)
# Initialize vocab with unique characters, including 'Ġ' if present
# Start with the first 256 ASCII characters
unique_chars = [chr(i) for i in range(256)]
# Extend unique_chars with characters from processed_text that are not already included
unique_chars.extend(char for char in sorted(set(processed_text)) if char not in unique_chars)
# Optionally, ensure 'Ġ' is included if it is relevant to your text processing
if 'Ġ' not in unique_chars:
unique_chars.append('Ġ')
# Now create the vocab and inverse vocab dictionaries
self.vocab = {i: char for i, char in enumerate(unique_chars)}
self.inverse_vocab = {char: i for i, char in self.vocab.items()}
# Add allowed special tokens
if allowed_special:
for token in allowed_special:
if token not in self.inverse_vocab:
new_id = len(self.vocab)
self.vocab[new_id] = token
self.inverse_vocab[token] = new_id
# Tokenize the processed_text into token IDs
token_ids = [self.inverse_vocab[char] for char in processed_text]
# BPE steps 1-3: Repeatedly find and replace frequent pairs
for new_id in range(len(self.vocab), vocab_size):
pair_id = self.find_freq_pair(token_ids, mode="most")
if pair_id is None: # No more pairs to merge. Stopping training.
break
token_ids = self.replace_pair(token_ids, pair_id, new_id)
self.bpe_merges[pair_id] = new_id
# Build the vocabulary with merged tokens
for (p0, p1), new_id in self.bpe_merges.items():
merged_token = self.vocab[p0] + self.vocab[p1]
self.vocab[new_id] = merged_token
self.inverse_vocab[merged_token] = new_id
def encode(self, text):
"""
Encode the input text into a list of token IDs.
Args:
text (str): The text to encode.
Returns:
List[int]: The list of token IDs.
"""
tokens = []
# Split text into tokens, keeping newlines intact
words = text.replace("\n", " \n ").split() # Ensure '\n' is treated as a separate token
for i, word in enumerate(words):
if i > 0 and not word.startswith("\n"):
tokens.append("Ġ" + word) # Add 'Ġ' to words that follow a space or newline
else:
tokens.append(word) # Handle first word or standalone '\n'
token_ids = []
for token in tokens:
if token in self.inverse_vocab:
# token is contained in the vocabulary as is
token_id = self.inverse_vocab[token]
token_ids.append(token_id)
else:
# Attempt to handle subword tokenization via BPE
sub_token_ids = self.tokenize_with_bpe(token)
token_ids.extend(sub_token_ids)
return token_ids
def tokenize_with_bpe(self, token):
"""
Tokenize a single token using BPE merges.
Args:
token (str): The token to tokenize.
Returns:
List[int]: The list of token IDs after applying BPE.
"""
# Tokenize the token into individual characters (as initial token IDs)
token_ids = [self.inverse_vocab.get(char, None) for char in token]
if None in token_ids:
missing_chars = [char for char, tid in zip(token, token_ids) if tid is None]
raise ValueError(f"Characters not found in vocab: {missing_chars}")
can_merge = True
while can_merge and len(token_ids) > 1:
can_merge = False
new_tokens = []
i = 0
while i < len(token_ids) - 1:
pair = (token_ids[i], token_ids[i + 1])
if pair in self.bpe_merges:
merged_token_id = self.bpe_merges[pair]
new_tokens.append(merged_token_id)
i += 2 # Skip the next token as it's merged
can_merge = True
else:
new_tokens.append(token_ids[i])
i += 1
if i < len(token_ids):
new_tokens.append(token_ids[i])
token_ids = new_tokens
return token_ids
def decode(self, token_ids):
"""
Decode a list of token IDs back into a string.
Args:
token_ids (List[int]): The list of token IDs to decode.
Returns:
str: The decoded string.
"""
decoded_string = ""
for token_id in token_ids:
if token_id not in self.vocab:
raise ValueError(f"Token ID {token_id} not found in vocab.")
token = self.vocab[token_id]
if token.startswith("Ġ"):
# Replace 'Ġ' with a space
decoded_string += " " + token[1:]
else:
decoded_string += token
return decoded_string
@lru_cache(maxsize=None)
def get_special_token_id(self, token):
return self.inverse_vocab.get(token, None)
@staticmethod
def find_freq_pair(token_ids, mode="most"):
pairs = Counter(zip(token_ids, token_ids[1:]))
if mode == "most":
return max(pairs.items(), key=lambda x: x[1])[0]
elif mode == "least":
return min(pairs.items(), key=lambda x: x[1])[0]
else:
raise ValueError("Invalid mode. Choose 'most' or 'least'.")
@staticmethod
def replace_pair(token_ids, pair_id, new_id):
dq = deque(token_ids)
replaced = []
while dq:
current = dq.popleft()
if dq and (current, dq[0]) == pair_id:
replaced.append(new_id)
# Remove the 2nd token of the pair, 1st was already removed
dq.popleft()
else:
replaced.append(current)
return replaced
Training the tokenizer is essentially a search for the best pairs. After training, bpe_merges holds those pairs.
def main():
with open("config.yaml") as f:
cfg = yaml.safe_load(f)["tokenizer"]
with open(cfg["sample_file"], encoding="utf-8") as f:
text = f.read(cfg["sample_chars"]) # first N characters, not the whole 500 MB
tokenizer = BPETokenizerSimple()
tokenizer.train(text, vocab_size=1000, allowed_special={"<|endoftext|>"})
print(len(tokenizer.vocab))
print(len(tokenizer.bpe_merges))
input_text = "Jack embraced beauty through art and life."
token_ids = tokenizer.encode(input_text)
print("token_ids:", token_ids)
print("Number of characters:", len(input_text))
print("Number of token IDs:", len(token_ids))
for token_id in token_ids:
print(f"{token_id} -> {tokenizer.decode([token_id])}")
print(tokenizer.decode(tokenizer.encode("This is some text.")))
if __name__=='__main__':
main()
Output:
$ python tokenizer/bpe_simple.py
1000
718
token_ids: [74, 468, 107, 256, 364, 791, 468, 333, 315, 351, 441, 121, 291, 360, 117, 334, 309, 114, 116, 309, 110, 100, 256, 356, 448, 46]
Number of characters: 42
Number of token IDs: 26
74 -> J
468 -> ac
107 -> k
256 ->
364 -> em
791 -> br
468 -> ac
333 -> ed
315 -> b
351 -> ea
441 -> ut
121 -> y
291 -> th
360 -> ro
117 -> u
334 -> gh
309 -> a
114 -> r
116 -> t
309 -> a
110 -> n
100 -> d
256 ->
356 -> li
448 -> fe
46 -> .
This is some text.
Token 256 is a lone space (Ġ). The word "Ġembraced" is not in the vocabulary, so it is split into characters, and Ġ did not merge with the next piece. The space was left as a separate token.
Let’s take the ready-made tiktoken library and see how it converts text into tokens and back.
import tiktoken
import yaml
def main():
tokenizer = tiktoken.get_encoding("gpt2")
text = "Jack embraced beauty through art and life."
integers = tokenizer.encode(text)
print("integers:", integers)
print([tokenizer.decode([i]) for i in integers])
decoded = tokenizer.decode(integers)
print("decoded:", decoded)
# Special tokens: the same string can be encoded in two different ways.
text = "end of book<|endoftext|>next book"
# 1. Default: tiktoken refuses to encode text that contains a special token.
try:
tokenizer.encode(text)
except ValueError as e:
print("default: ValueError:", str(e).splitlines()[0])
# 2. Allowed: "<|endoftext|>" becomes ONE special token, id 50256.
ids = tokenizer.encode(text, allowed_special={"<|endoftext|>"})
print("allowed:", [tokenizer.decode([i]) for i in ids], ids)
# 3. Treated as plain text: the same characters become ordinary pieces.
ids = tokenizer.encode(text, disallowed_special=())
print("as text:", [tokenizer.decode([i]) for i in ids], ids)
with open("config.yaml") as f:
cfg = yaml.safe_load(f)["tokenizer"]
with open(cfg["sample_file"], encoding="utf-8") as f:
text = f.read(10_000_000)
ids = tokenizer.encode(text, allowed_special={"<|endoftext|>"})
print(f"{len(text) / len(ids):.2f} chars per token")
if __name__=="__main__":
main()
Output:
$ python tokenizer/tiktoken_sample.py
integers: [14295, 18079, 8737, 832, 1242, 290, 1204, 13]
['Jack', ' embraced', ' beauty', ' through', ' art', ' and', ' life', '.']
decoded: Jack embraced beauty through art and life.
default: ValueError: Encountered text corresponding to disallowed special token '<|endoftext|>'.
allowed: ['end', ' of', ' book', '<|endoftext|>', 'next', ' book'] [437, 286, 1492, 50256, 19545, 1492]
as text: ['end', ' of', ' book', '<', '|', 'end', 'of', 'text', '|', '>', 'next', ' book'] [437, 286, 1492, 27, 91, 437, 1659, 5239, 91, 29, 19545, 1492]
3.40 chars per token
The string <|endoftext|> can be encoded in two ways. With allowed_special it becomes a single special token with id 50256 - this is exactly how the model learns that a book has ended. With disallowed_special=() it is just 13 characters, and they are split into the ordinary tokens <, |, end, of, text, |, >. By default tiktoken does not guess and raises an exception. This is a safeguard: if a user types <|endoftext|> in a prompt, they must not get a control token. We inserted our book separators ourselves, so we allow them explicitly.
Summary:
- Simple BPE: vocabulary of 1000, training on 200k characters takes ~14 s, the sentence is 26 tokens.
- tiktoken gpt2: vocabulary of 50257, the same sentence is 8 tokens.
- On our books ~3.4 characters per token: 14.3 GB ≈ 4.2 billion tokens.
On to the next part - embeddings.