latent state // log
Nov 13, 2026 // NLP · ML // 8 min

LLM [3] Tokenizer

↓ .md

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:

  1. 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.
  2. 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.
  3. Keeps merging until there is no pair left that could be merged.
  4. 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.