Tokenization Explained !

Models don't read words

When you type a prompt, the model never sees your letters. Before anything else happens, a tokenizer chops the text into pieces and swaps each piece for a number. The model only ever sees those numbers, and everything it writes back is a list of numbers that the tokenizer turns into text again.

So the tokenizer decides what the model's "atoms" are. That choice explains a surprising amount of LLM weirdness: why models struggle to count the letters in a word, why the same sentence costs more in Hindi than in English, and why Elephant and elephant can look like completely different things to a model.

This post builds two tokenizers from scratch. One is the simplest thing that could possibly work, and the other is the method behind GPT-2, GPT-4 and Llama 3.

Characters, bytes and tokens

These three words get mixed up all the time, and they mean different things:

• Character: a Unicode code point, which is what Python gives you when you loop over a string. "a", "न" and "😄" are one character each.
• Byte: a number from 0 to 255. UTF-8 stores every character as 1 to 4 bytes: "a" is the single byte 97, while "😄" is the four bytes 240 159 152 132. Those 256 values are enough to write any text in any language.
• Token: an ID in the tokenizer's vocabulary. What a token stands for depends on the tokenizer.

Keep these apart and the rest of the post is easy.

Tokenizer 1: one character, one token

The simplest possible tokenizer: collect every unique character in the training text, sort them, and use each one's position as its ID.

class CharLevelTokenizer:
    def fit(self, corpus):
        self.vocab = sorted(set(corpus))
        self.vocab_size = len(self.vocab)
        self.encodings = {ch: i for i, ch in enumerate(self.vocab)}   # stoi: char -> ID
        self.decodings = {i: ch for i, ch in enumerate(self.vocab)}   # itos: ID -> char

    def encode(self, text) -> list[int]:
        unknown = sorted(set(text) - self.encodings.keys())
        if unknown:
            raise ValueError(f"Characters not in the vocabulary: {unknown}")
        return [self.encodings[ch] for ch in text]

    def decode(self, tokens) -> str:
        return "".join(self.decodings[i] for i in tokens)

That's the whole thing (the version in the repo adds a couple of error checks). Fit it on one sentence and you get a 21-character vocabulary:

tokenizer = CharLevelTokenizer()
tokenizer.fit("My name is abhishek sharma. I love deep learning.")

print(tokenizer.vocab)
# [' ', '.', 'I', 'M', 'a', 'b', 'd', 'e', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 'v', 'y']

ids = tokenizer.encode("I love India")
print(ids)                    # [2, 0, 12, 15, 19, 7, 0, 2, 14, 6, 10, 4]
print(tokenizer.decode(ids))  # I love India

Space is ID 0 and . is ID 1. Uppercase letters come before lowercase ones because sorting follows Unicode code point order.

It works, and it's honest about what it doesn't know. Ask it to encode "xyz" and it refuses:

ValueError: Characters not in the vocabulary: ['x', 'z']

y is fine because it appears in "My". x and z never showed up during fit, so the tokenizer has no ID for them.

Where character-level falls short

• Sequences are long. One token per character means "I love India" is 12 tokens. A model's context window and compute both scale with the number of tokens, so that's expensive.
• Unseen characters break it. Any emoji, accented letter or symbol missing from the training text is an error. You can add an <unk> ("unknown") token, but then the model can't tell what it's missing.
• The model has to learn spelling from scratch. It sees e, l, e, p... and has to work out on its own that those letters together mean an animal.

We want bigger pieces for common text, and a fallback that can always handle anything. That's BPE.

Tokenizer 2: Byte Pair Encoding

BPE comes from a 1994 compression algorithm, and the idea fits in one sentence: start with single bytes, then keep merging the most common neighbouring pair into a new token.

Training goes like this:

1. Convert the training text to UTF-8 bytes. The starting vocabulary is the 256 possible byte values, tokens 0 to 255.
2. Count every pair of neighbouring tokens.
3. Take the most frequent pair and give it a new ID, starting at 256.
4. Replace every occurrence of that pair with the new token.
5. Repeat until the vocabulary is as big as you asked for.

Starting from bytes instead of characters is the key move. Every possible text is just a sequence of bytes, and all 256 bytes are in the vocabulary from the start. There's no such thing as an unknown character.

Watch it learn

Here's BPE on the string "aaabdaaabac", learning 4 merges:

Eleven bytes become four tokens. Notice how each new token is built on top of earlier ones: 257 is "256 followed by a". The list of merges is the tokenizer. Nothing else is learned.

The code

Training is two helpers and a loop. One helper counts pairs, the other replaces a pair everywhere it appears:

def _count_pairs(self, tokens):
    pair_freq = {}
    for pair in zip(tokens, tokens[1:]):
        pair_freq[pair] = pair_freq.get(pair, 0) + 1
    return pair_freq

def _merge_list(self, tokens, pair, idx):
    merged, i = [], 0
    while i < len(tokens):
        if i < len(tokens) - 1 and tokens[i] == pair[0] and tokens[i + 1] == pair[1]:
            merged.append(idx)
            i += 2  # skip both halves of the pair
        else:
            merged.append(tokens[i])
            i += 1
    return merged

def fit(self, train_data, vocab_size=500):
    self.tokens = list(train_data.encode("utf-8"))
    for merge in range(vocab_size - 256):
        pair_freq = self._count_pairs(self.tokens)   # recount every round
        if not pair_freq:
            break                                    # everything merged into one token
        pair = max(pair_freq, key=pair_freq.get)
        idx = 256 + merge
        self.tokens = self._merge_list(self.tokens, pair, idx)
        self.merges[pair] = idx
    self._build_vocab()

The vocabulary (what bytes each token stands for) is rebuilt from the merges. Each merged token is just the bytes of its two halves joined together:

def _build_vocab(self):
    self.vocab = {i: bytes([i]) for i in range(256)}
    for (a, b), idx in self.merges.items():      # dicts keep insertion order
        self.vocab[idx] = self.vocab[a] + self.vocab[b]

Encoding and decoding

Decoding is easy: look up each token's bytes, join them and decode them as UTF-8.

Encoding is the subtle part. To encode new text you convert it to bytes and replay the merges in the order they were learned. Order matters because later merges are built from earlier ones: token 257 = (256, a) can only form once 256 exists. So at each step we pick the pair in the text that was learned earliest, which is the one with the smallest new ID:

def encode(self, text) -> list[int]:
    tokens = list(text.encode("utf-8"))
    while len(tokens) >= 2:
        pairs = set(zip(tokens, tokens[1:]))
        pair = min(pairs, key=lambda p: self.merges.get(p, float("inf")))
        if pair not in self.merges:
            break                                    # nothing left to merge
        tokens = self._merge_list(tokens, pair, self.merges[pair])
    return tokens

def decode(self, tokens) -> str:
    text_bytes = b"".join(self.vocab[t] for t in tokens)
    return text_bytes.decode("utf-8", errors="replace")

What BPE learns from real text

Toy strings are nice, but the fun starts on real text. I trained a 500-token vocabulary (244 merges) on a 2,622-byte Wikipedia passage about the desert elephants of Namibia.

The first merges are pure English statistics:

256 -> b'e '      (an "e" at the end of a word)
257 -> b'th'
258 -> b's '
259 -> b'er'
260 -> b'an'
261 -> b' th'
262 -> b'in'
263 -> b'd '
264 -> b'ar'
265 -> b't '

By merge 11 it has built ' the '. At merge 148 it learns desert elephants , 17 bytes squashed into one ID, because that phrase appears all over the article. It's the longest token in the vocabulary, and it shows up before the tokenizer learns elephant on its own (merge 192). BPE doesn't care about words, only about what repeats.

The training text goes from 2,622 bytes to 940 tokens, a 2.79× compression. Now look at how the trained tokenizer splits some new strings:

There's a lot packed into that table:

• Capital letters change everything. elephants is 2 tokens, but Elephant is 4, because the capitalised word barely appeared in training. Real tokenizers have the same quirk: hello, Hello and HELLO can get completely different tokens.
• The model never sees letters. strawberry arrives as s tr a w b er r y. Asking "how many r's?" means the model has to remember what's inside er and r. This is the root of the famous strawberry problem.
• Numbers get chopped up arbitrarily. My tiny corpus has few digits, so every digit stays separate. Bigger tokenizers merge common digit groups, which is part of why LLMs find arithmetic awkward.
• Languages the tokenizer didn't train on cost more. नमस्ते is 6 characters but 18 tokens, because no Hindi was in the training text, so every byte stays on its own. Real tokenizers are trained on far more languages, but the same effect shows up at a smaller scale: the same sentence often takes more tokens, so costs more and fits less in the context window, in languages that are rarer in the training data.

And unseen text never fails. The emoji in "Unicode is not that scary! 😄" was nowhere in the training data, so it simply falls back to its four bytes:

[b'U', b'n', b'ic', b'o', b'd', b'e ', b'is ', b'no', b't', b' th', b'at ', b's', b'c', b'ar', b'y', b'!', b' ', b'\xf0', b'\x9f', b'\x98', b'\x84']
Round trip OK: True

Character-level vs BPE

What real tokenizers add

My BPE is the real algorithm, but production tokenizers add a few things on top:

• Pre-splitting with a regex. My version merges across the whole text, which is how it ends up with tokens like e and desert elephants that cross word boundaries. GPT-style tokenizers first split text into words, numbers and punctuation, and only merge inside each piece. That keeps the vocabulary from filling up with one corpus's favourite phrases.
• Much bigger vocabularies. 500 tokens is a toy. GPT-2 uses 50,257, GPT-4's tokenizer about 100,000 and Llama 3 about 128,000. A bigger vocabulary gives shorter sequences, but a bigger embedding table.
• Special tokens like <|endoftext|> that mark document boundaries or chat turns, and that are never produced by merging ordinary text.
• Speed. Mine is pure Python and recounts every pair after every merge, which is fine for a few kilobytes and painful for gigabytes. Libraries like tiktoken, Hugging Face tokenizers and SentencePiece are written in Rust or C++.

Takeaways

1. Models read token IDs, not text. The tokenizer decides what the model's smallest units are.
2. Character-level tokenization is simple and readable, but gives long sequences and breaks on anything it hasn't seen.
3. BPE starts from 256 bytes, so it can encode anything, then merges frequent pairs so common text gets short.
4. The ordered list of merges is the entire learned tokenizer. Encoding replays them in order.
5. Plenty of famous LLM quirks (letter counting, arithmetic, case sensitivity, the cost of other languages) are really tokenizer quirks.

Written by Abhi Sharma

Data and AI @ Google | I love to write, explain and build things.