Chapter 1

From Text to Token IDs

A language model reads integers, not text. This chapter builds the artifact that produces those integers: a minimal BPE tokenizer for learning, then the production tokenizer the rest of the book uses, checked against GPT-2's published token IDs.

← Back to the book overview and code


This chapter covers

A GPT-2 model does not read text. It has no notion of a letter, and no machine ever has.

It reads integers. Everything this book builds — attention, the model, the training loop — starts from a list of integers. This chapter is about the mechanics of producing that list.

We begin at the end, with the finished tokenizer.

1.1 Text in, IDs out

The tokenizer we end up with is mbpe. Here it is loading the GPT-2 vocabulary and round-tripping a string:

from bpe.tokenizer import Tokenizers


def main() raises:
    var gpt2 = Tokenizers.get[Tokenizers.gpt2]()
    var ids = gpt2.encode("hello world")
    print(gpt2.decode(ids))

Source: the Mojo API example in the mbpe README.

And the IDs behind the round trip:

from bpe.tokenizer import Tokenizers


def main() raises:
    var gpt2 = Tokenizers.get[Tokenizers.gpt2]()
    var ids = gpt2.encode("hello world")
    print(ids)  # [31373, 995]

The same call, printing the IDs instead.

Eleven characters go in and two integers come out: 31373 and 995. These are the same two IDs OpenAI’s GPT-2 produces for the same string.

Where does the tokenizer sit in the pipeline? The whole path is:

"hello world" -> [tokenizer] -> [31373, 995] -> model -> [31373, 995] -> [tokenizer] -> "hello world"

The tokenizer stands on both ends of the model. Everything between the arrows works on IDs. The IDs select embeddings. The Transformer layers transform those vectors, and the output layer produces scores over the vocabulary. The model never needs to know how the original text was split.

That decision is made earlier, once, when the tokenizer is trained on a corpus and the mapping is frozen. ID 31373 means hello for GPT-2 because the weights were trained against that mapping. The model never learns the merge history behind the vocabulary, but it depends on the interface: the same ID must select the same embedding and output class every time. Change the mapping without retraining, and the weights are intact but meaningless.

Reading the Mojo. The listings use a handful of Mojo constructs throughout. var declares a mutable local variable. def … raises means the function can throw an error. A trailing ^ moves ownership out of the function instead of copying. ref borrows a value without copying it. comptime marks a compile-time constant, and Struct[T] in BPETokenizer[T] or Tokenizers.get[T] passes the pre-tokenizer as a compile-time parameter, so each choice compiles to its own specialized code. List and Dict are the growable array and hash table.

The two IDs are hello and ` world. The space belongs to the second token. Without the space, world is a different token, 6894. With two spaces between the words you get three IDs, [31373, 220, 995]`: the extra space becomes a token of its own. The tokenizer encodes exact bytes, not words.

A tokenizer does not necessarily give every word or character its own token. It can represent a piece of text as one token or split it across several, depending on which pieces its vocabulary contains.

GPT-2, for example, splits the Hindi word नमस्ते into twelve token IDs and the emoji 😀 into two. Neither appears as a single token in its vocabulary. Other tokenizers, with different vocabularies, may split the same text differently.

These differences matter. When a tokenizer needs more tokens to represent the same text, the model has a longer sequence to process. Some languages therefore require more tokens than others to express comparable text. Exercise 1.5 lets you measure this difference.

The rest of the chapter explains how those numbers are decided. We work in three stages: first the idea, then a small implementation you can read in one sitting, then the real one.

Code for this chapter

Repository Role in this chapter Revision
simple_bpe A small tokenizer, built for learning 012a278
mbpe The tokenizer we use for the rest of the book via tenmo

Every listing below names the file and the function it comes from. The simple_bpe listings also print their line range at the pinned revision. Nothing is rewritten for the page, and no mbpe revision is pinned here — it reaches this book through tenmo, which owns the pin. Three short call-site snippets — the ID print in 1.1, the check in 1.8, and the loop in Exercise 1.5 — are adapted from those listings and were verified by running under the pinned revisions. The validation scripts that check mbpe against tiktoken live in validate/ch01/; pixi run validate re-runs them.

simple_bpe follows the BPE walkthrough in the Hugging Face LLM Course (chapter 6, section 5), and its README says plainly that it is for learning. We use it the same way. It is not the tokenizer we carry forward.

1.2 Why not words, and why not characters

Two obvious designs come to mind. Both fail, in opposite directions.

One ID per word. The vocabulary is a dictionary of every word in the training text. This is easy to build and it breaks the first time the model sees a word it has not seen. A tokenizer built on a short story has no ID for “Hello” if the story never says it. Real text is full of names, typos, code identifiers and other languages. A word-level vocabulary either grows without bound or throws information away.

One ID per character. Now nothing is ever unknown. But sequences get long: the model must piece words together from letters before it can do anything useful, and attention compares every position with every other, so wasted length is expensive.

Subword tokenization sits between the two. Common words become a single token. Rare words are spelled out in pieces. Nothing is ever unknown.

Representation Vocabulary Sequence length Unseen words
Words Large Short Poor
Characters or bytes Small Long Excellent
Subwords, with a byte fallback Moderate Moderate Excellent

Two costs explain why neither extreme survives.

Length is expensive. Attention compares every position with every other. Fifty tokens means 2,500 pairs. A hundred means 10,000. Spelling everything in characters pays that bill for nothing, and makes the model relearn that t-h-e is a word.

Vocabulary is expensive too. Every entry owns a row in the embedding table. GPT-2’s smallest model uses 768 dimensions, so its 50,257 rows hold about 39 million numbers before a single attention layer exists. A bigger vocabulary buys shorter sequences and fatter tables. The tokenizer spends parameters before the transformer sees anything.

BPE is the most widely used way to find those pieces, and the one GPT-2 uses. The next section works through it by hand.

1.3 BPE by hand

BPE learns its pieces from data. The training procedure fits in five lines:

  1. Split the text into words and count how often each word occurs.
  2. Start the vocabulary with every distinct character.
  3. Count every adjacent pair of tokens, weighted by word frequency.
  4. Merge the most frequent pair into one new token and remember the rule.
  5. Repeat from step 3 until the vocabulary is the size you asked for.

Here is the example from the Hugging Face course. Five words, with counts:

word count
hug 10
pug 5
pun 12
bun 4
hugs 5

The starting vocabulary is the characters b g h n p s u. Count the adjacent pairs:

pair count where it comes from
u g 20 hug (10) + pug (5) + hugs (5)
p u 17 pug (5) + pun (12)
u n 16 pun (12) + bun (4)
h u 15 hug (10) + hugs (5)

u g wins. It becomes a new token, ug, and every word is rewritten:

h ug    p ug    p u n    b u n    h ug s

Count again. Now u n leads with 16, so un is the second token. After that, h ug has 15, so hug is the third:

hug    p ug    p un    b un    hug s

Three merges, three new tokens, three rules, in this order:

(u, g) -> ug
(u, n) -> un
(h, ug) -> hug

The order matters. The third rule builds on the first: hug cannot exist until ug does.

To encode new text, split it into characters and replay the rules in the order they were learned. Take bug:

b u g   ->  b ug      after rule 1
            b ug      rules 2 and 3 find nothing

Two tokens remain: b and ug. Each carries an ID — its position in the vocabulary — and the list of IDs is what the model receives.

That is the whole algorithm. The rest of the chapter is making it work on real text.

1.4 A minimal tokenizer, in full

simple_bpe is 431 lines of Mojo in one file. It trains, encodes, decodes, saves and loads. We look at the parts that correspond to the five-line recipe above.

Cutting text into words

BPE merges only inside a word, so the text must be split into words first. simple_bpe uses two rules: every space becomes a marker, Ġ, glued to the front of the next word, and every period becomes its own word. The marker is the one GPT-2 uses. It lets the decoder restore each space exactly.

simple_bpe/tokenizer.mojo, lines 98–112 (the body of PreTokenizer.split)

        var splits = (
            StringSlice(text)
            # " " -> " Ġ": keep a space as the cut point and add the marker after it.
            .replace(" ", " " + spacer)
            # "." -> " .": add a cut point before every period.
            .replace(".", " .")
            # Cut at every space. The separators vanish; the marker stays.
            .split(" ")
        )
        # The pieces are string views into the text above. Copy each one into
        # its own String so the result owns its data.
        var result = List[String](capacity=len(splits))
        for split in splits:
            result.append(String(from_utf8=split.as_bytes()))
        return result^

"hello world." becomes ["hello", "Ġworld", "."]. Nothing else is handled: commas, digits, contractions, and newlines stay attached to whatever is next to them. Section 1.5 returns to this.

The training loop

Steps 3, 4 and 5 of the recipe are this loop. Each pass adds exactly one token to the vocabulary.

simple_bpe/tokenizer.mojo, lines 188–215

        # Step 5. The merge loop. Each pass adds exactly one vocabulary entry.
        self.merges = Dict[Tuple[String, String], String]()
        while len(self.vocab) < vocab_size:
            # Count every adjacent pair across all words, weighted by how often
            # each word occurs.
            var pair_freqs = _compute_pair_freqs(splits, word_freqs)
            # No pairs means every word is already a single token.
            if len(pair_freqs) == 0:
                break
            # Find the most frequent pair. The comparison is strict (<), so on a
            # tie the pair seen first in iteration order stays the winner.
            # max_freq == -1 only matters on the first pair: it accepts it.
            var best_pair: Tuple[String, String] = ("", "")
            var max_freq = -1
            for pair_freq in pair_freqs.items():
                var pair = pair_freq.key
                var freq = pair_freq.value
                if max_freq == -1 or max_freq < freq:
                    best_pair = pair
                    max_freq = freq
            # Rewrite every word so the winning pair becomes one token.
            _merge_pair(best_pair[0], best_pair[1], splits, word_freqs)
            # Record the new token. Appending to vocab gives it the next free
            # ID, and inserting into merges keeps the rules in learned order.
            var joined = best_pair[0].copy() + best_pair[1].copy()
            self.merges[best_pair] = joined
            self.vocab.append(joined)
            self.stoi[joined] = len(self.vocab) - 1

Read it against the five-line recipe. _compute_pair_freqs is the pair table:

simple_bpe/tokenizer.mojo, lines 380–392 (the body of _compute_pair_freqs)

    var pair_freqs = Dict[Tuple[String, String], Int]()
    for word_freq in word_freqs.items():
        var word = word_freq.key
        var freq = word_freq.value
        ref split = splits[word]
        # A word reduced to one token has no pairs left.
        if len(split) == 1:
            continue
        # Pair each token with the one to its right.
        for i in range(len(split) - 1):
            var pair = (split[i], split[i + 1])
            pair_freqs[pair] = pair_freqs.get(pair, 0) + freq
    return pair_freqs^

_merge_pair is the rewrite from u g to ug:

simple_bpe/tokenizer.mojo, lines 412–431 (the body of _merge_pair)

    for word in word_freqs:
        ref split = splits[word]
        if len(split) == 1:
            continue
        var i = 0
        while i < len(split) - 1:
            if split[i] == a and split[i + 1] == b:
                # Rebuild the list: everything before i, the joined token,
                # everything after i + 1. The merged token is at i, so i stays
                # put. The joined token never equals a, so it cannot match
                # again at the same position, and the next pass moves on.
                split = (
                    [e for e in split[:i]]
                    + [a + b]
                    + [e for e in split[i + 2 :]]
                )
            else:
                i += 1
        # Store the updated list back under the word.
        splits[word] = split.copy()

Two details matter here. The pair counts are weighted by word frequency, so a word that appears ten times is counted ten times. And when two pairs tie, the one seen first wins. That is a simple rule, and it makes training deterministic: the same corpus gives the same merges.

Encoding is replaying

Encoding walks the merge rules in the order they were learned, and applies each one to every word.

simple_bpe/tokenizer.mojo, lines 232–267 (the body of _tokenize)

        if text.byte_length() == 0:
            return List[String]()
        # Same word split as in training. The words must be cut the same way,
        # or the learned rules would not line up with the pieces.
        var words = PreTokenizer.split(text)
        # One list of single-character tokens per word.
        var splits = [
            [chr(Int(cp)) for cp in word.codepoints()]
            for word in words
        ]
        # merges.items() yields rules in the order they were inserted, which
        # is the order they were learned.
        for pair_merge in self.merges.items():
            ref pair = pair_merge.key
            ref merge = pair_merge.value
            for idx, split in enumerate(splits):
                var i = 0
                var split_copied = split.copy()
                # Walk the word left to right looking for the rule's pair.
                while i < len(split_copied) - 1:
                    if split_copied[i] == pair[0] and split_copied[i + 1] == pair[1]:
                        # Replace the two tokens with the joined token: keep
                        # everything before i, insert the joined token, keep
                        # everything after i + 1. i is not advanced; the
                        # joined token sits at i and is compared with its new
                        # right neighbour on the next pass.
                        split_copied = (
                            [e for e in split_copied[:i]]
                            + [merge]
                            + [e for e in split_copied[i + 2 :]]
                        )
                    else:
                        i += 1
                splits[idx] = split_copied^
        # Join the per-word lists into one flat list of tokens.
        return [item for sublist in splits for item in sublist]

This is the five-line procedure, written out. It is also, as we will see, the slow way to do it.

Run it

git clone https://github.com/ratulb/simple_bpe
cd simple_bpe
pixi install
pixi run mojo main.mojo

The tests in main.mojo train on small corpora, check that encode followed by decode returns the input, and check that a saved tokenizer loads back identically. They are the shortest documentation of the API.

The next section shows where this readable tokenizer breaks.

1.5 Limits of the small tokenizer

A tokenizer written to be read has shortcuts. Three of them matter, and each one shows up on real text.

Unseen characters

simple_bpe starts its vocabulary from the characters in the training text. Anything else has no entry. Its answer is a placeholder token, <UNK>, at ID 0.

The test says it directly. Train on "abc", then encode "xyz":

simple_bpe/main.mojo, lines 5–15

def test_unk_fallback() raises:
    var corpus = List[String]()
    corpus.append(String("abc"))
    var tok = BPETokenizer()
    tok.train(corpus, 12)
    var ids = tok.encode(String("xyz"))
    assert_equal(len(ids), 3)
    assert_equal(ids[0], 0)
    assert_equal(ids[1], 0)
    assert_equal(ids[2], 0)
    assert_equal(tok.decode(ids), "<UNK><UNK><UNK>")

Three characters in, three <UNK> out. The text is gone, and no decoder can bring it back. A model trained on this tokenizer cannot tell “xyz” from any other three unknown characters. The Hugging Face course version raises an error here instead.

A pre-tokenizer with two rules

It handles spaces and periods, and nothing else. "don't", "hello," and the newline in "line one\nline two" all stay glued to the words beside them, in chunks that no model should be asked to learn from. The two splitters on the same word show the difference:

"don't" -> ["don't"]        simple_bpe: one glued chunk
"don't" -> ["don", "'t"]    GPT-2: the contraction is split off

GPT-2’s tokenizer separates letters from digits from punctuation from whitespace, and its merges were learned under that splitting. Without the same splitting, the same merges do not apply.

Encoding by replaying every rule

Encoding applies every rule to every word, in order. The work grows with the number of rules times the amount of text. A real vocabulary has fifty thousand tokens. This is a teaching implementation and it behaves like one.

Training has a similar shape: it recounts all the pairs after every merge.

None of these are bugs. They are the differences between a tokenizer written to be read and one used to train a model. The next section removes them one at a time.

1.6 mbpe: a production-grade tokenizer

mbpe is the tokenizer the rest of the book uses. It is byte-level, compatible with tiktoken’s file format, and written in Mojo with Python bindings. Its design has one organizing idea:

The BPE core knows only BPE. Everything that distinguishes one tokenizer family from another lives in a pre-tokenizer.

Every tokenizer in this chapter is one pipeline with three stages:

"hello  world" -> [pre-tokenizer] -> ["hello", " ", " world"] -> [BPE merges] -> [31373, 220, 995]

Raw text enters, the pre-tokenizer splits it into pieces, and BPE merges turn each piece into IDs. The three limits from the last section each live in one stage, and the three fixes below land on the same stages in the same order. Two things follow: the canonical aaabdaaabac test that pins the algorithm, and the invariant behind replaying by rank.

Fix one: bytes instead of characters

mbpe does not start from the characters in the training text. It starts from all 256 possible byte values. Any text, in any language, is a sequence of bytes. Nothing is unknown.

The mapping below is how bytes are displayed. Printable ASCII and most of Latin-1 display as themselves. The remaining bytes, control characters, the space, and a few others, are assigned code points starting at 256, in order.

Source: mbpe’s bpe/tokenizer.mojo, inside BPETokenizer.__init__.

        var n = 0
        for b in range(256):
            var printable = False
            if b >= 0x21 and b <= 0x7E:
                printable = True
            elif b >= 0xA1 and b <= 0xAC:
                printable = True
            elif b >= 0xAE and b <= 0xFF:
                printable = True
            if printable:
                self.byte_to_cp[b] = b
            else:

                var cp = 256 + n
                self.byte_to_cp[b] = cp
                n += 1

Counting them: the bytes 0x00 to 0x20 are all non-printable, and space is the 33rd of them. It lands on code point 288, U+0120, the code point for Ġ. The marker in simple_bpe’s pre-tokenizer was never arbitrary. It is how GPT-2 shows a space.

Here is the mbpe version of the test from section 1.5. Same corpus, same unseen input:

Source: mbpe’s tests/test_tokenizer.mojo.

def test_byte_level_no_unk() raises:
    """Verify unknown byte sequences produce 3 distinct non-zero token IDs.
    Train on "abc", encode "xyz" — since our vocab is byte-level, every
    byte (including those unseen during training) maps to a known token ID.
    No UNK token is ever produced.
    """
    var corpus = List[String]()
    corpus.append(String("abc"))
    var tok = BPETokenizer()
    tok.train(corpus, 300)
    var ids = tok.encode(String("xyz"))
    assert_equal(len(ids), 3)
    assert_true(ids[0] != 0)
    assert_true(ids[1] != 0)
    assert_true(ids[2] != 0)
    assert_equal(tok.decode(ids), "xyz")

The result is three IDs, none of them zero, and the text decodes back exactly.

Fix two: a swappable pre-tokenizer

The pre-tokenizer is a Mojo trait. The core is generic over it, and the choice is made at compile time.

Source: mbpe’s bpe/pretokenizer.mojo, the start of the PreTokenizer trait.

trait PreTokenizer(Movable & Defaultable & Deinitable & Writable):

    comptime byte_map: ByteMapping

    @staticmethod
    @always_inline
    def byte_to_id(b: Int) -> Int:

        return b

    @staticmethod
    @always_inline
    def id_to_byte(rank: Int) -> Int:

        return rank

    def split[
        mut: Bool, //, origin: Origin[mut=mut]
    ](self, text: StringSpan[origin]) raises -> List[StringSpan[origin]]:

        var result = List[StringSpan[origin]]()
        result.reserve(1)
        result.append(text)
        return result^

The default split returns the whole text as one piece. Each implementation also supplies a name and its special tokens:

Source: mbpe’s bpe/pretokenizer.mojo, the end of the trait.

    @staticmethod
    def name() -> String:
        ...

    @staticmethod
    def special_tokens() -> Dict[String, Int]:
        return Dict[String, Int]()

The GPT-2 implementation tries a fixed list of matchers at each position, in this order: a contraction like 's, a run of letters, a run of digits, a run of punctuation, then the three whitespace cases. The first that matches wins, and the text is cut there.

Source: mbpe’s bpe/pretokenizer.mojo, GPT2Pretokenizer.

    @staticmethod
    @always_inline
    def _best_match[
        origin: Origin, //
    ](span: Span[UInt8, origin], pos: Int) raises -> Int:

        var m = GPT2Pretokenizer._match_contraction(span, pos)
        if m > 0:
            return m
        m = GPT2Pretokenizer._match_letter_run(span, pos)
        if m > 0:
            return m
        m = GPT2Pretokenizer._match_digit_run(span, pos)
        if m > 0:
            return m
        m = GPT2Pretokenizer._match_punct_run(span, pos)
        if m > 0:
            return m
        m = Self.match_trailing_all_ws(span, pos)
        if m > 0:
            return m
        m = Self.match_ws_not_before_nonws(span, pos)
        if m > 0:
            return m
        return Self.match_single_ws(span, pos)

    def split[
        mut: Bool, //, origin: Origin[mut=mut]
    ](self, text: StringSpan[origin]) raises -> List[StringSpan[origin]]:

        var result = List[StringSpan[origin]]()
        var n = text.byte_length()
        if n == 0:
            return result^
        var span = text.as_bytes()
        var pos = 0
        while pos < n:
            var best_len = GPT2Pretokenizer._best_match(span, pos)
            if best_len == 0:
                best_len = utf8_codepoint_byte_length(span[pos])
            var byte_span = span[pos : pos + best_len]
            result.append(StringSpan(unsafe_from_utf8=byte_span))
            pos += best_len
        return result^

These are hand-written byte scans, not a regular-expression engine. Together they implement GPT-2’s splitting rules. GPT-4 and GPT-4o get their own implementations behind the same trait, and a new tokenizer family means a new implementation, not a change to the core.

This is what “the GPT-2 tokenizer” means: three things have to match — the pre-tokenizer, the vocabulary, and the algorithm. Change any one and the IDs change. Load the right vocabulary under the wrong pre-tokenizer and the round trip still passes, because the bytes come back exactly. The IDs are wrong, and nothing complains.

A green round trip proves byte handling, not agreement with the model’s tokenizer. Verification is not “does it round-trip?” — it is “does it agree with the tokenizer the weights were trained against?” That is what §1.8 checks.

Fix three: merging by rank

simple_bpe replays all rules. mbpe asks a different question about each word: of the adjacent pairs here, which one is the oldest rule? Merge that one, then ask again. Stop when no adjacent pair has a rule.

This works because of how IDs are assigned. A merged token gets the next free ID, so a merged token’s ID is also its rank: smaller means learned earlier. The lookup table stores (left ID, right ID) -> merged ID, and the merged ID doubles as the priority.

Source: mbpe’s bpe/tokenizer.mojo, MergeLookup.set and .get.

    @always_inline
    def set(mut self, id1: Int, id2: Int, merged_id: Int):
        if id1 < CACHE_SIZE and id2 < CACHE_SIZE:
            self._fast.unsafe_ptr()[unsafe_offset=(id1 << CACHE_SHIFT) | id2] = merged_id
        else:
            self._slow[(id1 << ENCODE_SHIFT) | id2] = merged_id

    @always_inline
    def get(self, id1: Int, id2: Int) -> Int:
        if id1 < CACHE_SIZE and id2 < CACHE_SIZE:
            return self._fast.unsafe_ptr()[unsafe_offset=(id1 << CACHE_SHIFT) | id2]
        return self._slow.get((id1 << ENCODE_SHIFT) | id2, -1)

IDs below a fixed limit go into a flat array indexed by the pair. The rest go into a dictionary. Most merges involve common tokens, so most lookups hit the flat array.

With that table, merging one word is a loop:

Source: mbpe’s bpe/tokenizer.mojo, _merge_scan.

    @always_inline
    def _merge_scan[origin: Origin](
        self,
        ptr: Pointer[UInt8, origin],
        n: Int,
        dst: Pointer[Int, MutAnyOrigin],
    ) -> Int:

        self._copy_word_ids(ptr, n, dst)
        var len = n

        while len >= 2:
            var best_rank = -1
            var best_a = -1
            var best_b = -1
            var best_m = -1
            for i in range(len - 1):
                var merged = self.lookup_table.get(dst[unsafe_offset=i], dst[unsafe_offset=i + 1])
                if merged >= 0 and (best_rank < 0 or merged < best_rank):

                    best_rank = merged
                    best_a = dst[unsafe_offset=i]
                    best_b = dst[unsafe_offset=i + 1]
                    best_m = merged
            if best_rank < 0:

                break
            len = merge_inplace(dst, len, best_a, best_b, best_m)
        return len

Find the lowest-ranked pair. Merge it everywhere in the word. Repeat. merge_inplace does the rewrite without allocating:

Source: mbpe’s bpe/tokenizer.mojo, merge_inplace.

@always_inline
def merge_inplace(
    buf: Pointer[Int, MutAnyOrigin],
    n: Int,
    a: Int,
    b: Int,
    m: Int,
) -> Int:

    var w = 0
    var i = 0
    while i < n:
        if i < n - 1 and buf[unsafe_offset=i] == a and buf[unsafe_offset=i + 1] == b:

            buf[unsafe_offset=w] = m
            i += 2
        else:

            buf[unsafe_offset=w] = buf[unsafe_offset=i]
            i += 1
        w += 1
    return w

Short words use this scan. Longer words use a heap-based variant that applies the same merges without rescanning the word after each one (_merge_heap, beside this scan in the source). The full encoder is the pipeline made concrete:

Source: mbpe’s bpe/tokenizer.mojo, inside encode_ordinary.

        ref words = self.pt.split(text)

        var total_bytes = 0
        for word in words:
            total_bytes += word.byte_length()

        var result = IntArray(unsafe_uninit_length=total_bytes)
        var write_pos = 0
        var scratch = MergeScratch()
        var heap = BinaryHeap[Int]()
        for word in words:
            var ptr = word.unsafe_ptr()
            var n = word.byte_length()

            var dst = (result.unsafe_ptr().unsafe_offset(write_pos)).as_unsafe_any_origin()

            if n < 2:

                self._copy_word_ids(ptr, n, dst)
                write_pos += n
            elif n < SCAN_LIMIT:
                write_pos += self._merge_scan(ptr, n, dst)
            else:
                write_pos += self._merge_heap(ptr, n, dst, scratch, heap)

        scratch.free()

        result.resize(write_pos, 0)
        return result^

The encoder splits the text into words, copies each word’s bytes into IDs and merges them, then concatenates the results. That is the full encoder.

The same algorithm, pinned by a test

The textbook BPE example is the 11-byte string aaabdaaabac. Three merges reduce it to five tokens. The mbpe test suite trains on it and checks every ID:

Source: mbpe’s tests/test_tokenizer.mojo, test_wikipedia_example.

def test_wikipedia_example() raises:
    """Train with 3 merges on "aaabdaaabac" — the canonical BPE example
    from Wikipedia (https://en.wikipedia.org/wiki/Byte_pair_encoding).

    After 3 merges the 11-byte input should reduce to exactly 5 tokens:
      a=97, b=98, c=99, d=100 (ASCII)
      Z=aa=256, Y=ab|Za=257, X=ZY|Yb=258
    Final tokens: [258, 100, 258, 97, 99]
    """
    var corpus = List[String]()
    corpus.append(String("aaabdaaabac"))
    var tok = BPETokenizer()
    tok.train(corpus, 256 + 3)

    var ids = tok.encode(String("aaabdaaabac"))
    assert_equal(len(ids), 5)
    assert_equal(ids[0], 258)
    assert_equal(ids[1], 100)
    assert_equal(ids[2], 258)
    assert_equal(ids[3], 97)
    assert_equal(ids[4], 99)
    assert_equal(tok.decode(ids), "aaabdaaabac")

The bytes keep their ASCII values: a is 97, b is 98, c is 99, d is 100. Merged tokens start at 256, because 0 to 255 are taken by the bytes. The first merge, aa, becomes 256. The third merge builds on the first two and becomes 258. Same loop as the five-line recipe, now over bytes, and the IDs land where the textbook says they should.

Why replaying by rank is correct

A merged token’s bytes are always its two parents’ bytes joined. Its ID is also larger than either parent’s ID. So the lowest-ranked pair in a word is always the one training would have applied first, and every merge finds its parents already built.

Take three rules, learned in this order: l o becomes lo, lo w becomes low, low e becomes lowe. Encode lowering, a word those rules were never trained on:

l o w e r i n g
lo w e r i n g       rule 1
low e r i n g        rule 2
lowe r i n g         rule 3

The learned prefix fires on unseen input because the prefix is shared. That is why a bounded vocabulary covers unbounded text. The repo checks the invariant directly: test_tiktoken_merge_consistency, in mbpe/main.mojo.

What byte-level buys: the round trip

For any valid UTF-8 input, decode(encode(s)) returns s exactly. That is the point of starting from 256 bytes.

Two cases look like exceptions but are not. A vocabulary trained on one kind of text produces more and smaller pieces when it meets another; quality drops, but correctness does not. The real exceptions sit outside BPE: special tokens such as <|endoftext|>, which encode recognizes and encode_ordinary treats as plain text, and invalid UTF-8, where the bytes survive but a Mojo String may refuse to hold them.

Training, briefly

mbpe also trains. Its training keeps the pair counts up to date as merges happen instead of recounting from scratch, which is what makes it practical on large corpora. The README shows the call:

from bpe.tokenizer import BPETokenizer
from bpe.pretokenizer import GPT2Pretokenizer


def main() raises:
    var tok = BPETokenizer[GPT2Pretokenizer]()
    var corpus = List[String]()
    corpus.append("hello world")
    tok.train(corpus, 300)

Source: the training example in the mbpe README.

One thing training does not attempt: matching the exact merges OpenAI’s training run produced from its private data. That is not something we can reproduce. What we can do is load the vocabularies OpenAI published.

The next section covers the file format that holds those vocabularies.

1.7 Reading and writing tiktoken files

A .tiktoken file is one line per token: the token’s bytes in base64, a space, and its rank. The first lines of mbpe/data/gpt2.tiktoken:

IQ== 0
Ig== 1
Iw== 2

IQ== is the single byte !. GPT-2 gives it rank 0, then " rank 1, then # rank 2. The file lists the 256 byte tokens first, in GPT-2’s own order, followed by the merges in the order they were learned.

Loading it is one call:

Source: mbpe’s bpe/tokenizer.mojo, Tokenizers.

struct Tokenizers:

    comptime gpt2 = GPT2Pretokenizer
    comptime cl100k = GPT4Pretokenizer[ByteMapping.SEQUENTIAL]
    comptime o200k = GPT4Pretokenizer[ByteMapping.SHUFFLED]

    @staticmethod
    def get[T: PreTokenizer](filename: String = "") raises -> BPETokenizer[T]:
        var fname = T.name() if filename.byte_length() == 0 else filename
        var tok = BPETokenizer[T]()
        tok.load_tiktoken(_find_data_dir() + "/" + fname + ".tiktoken")
        return tok^

Tokenizers.get[Tokenizers.gpt2]() reads gpt2.tiktoken from the directory named by the MBPE_DATA_DIR environment variable, or from ./data/ if it is unset. Because the file format is shared, the same loader handles the other vocabularies in mbpe/data.

Two facts about the file are easy to miss. It has 50,256 lines for a vocabulary of 50,257, because <|endoftext|> is not in it: the file holds only mergeable tokens, and the pre-tokenizer declares the specials. And it has no merge list. The merges are recovered from the ranks, using the invariant from the last section. The ranks are the history.

The next section checks our tokenizer against GPT-2’s published IDs.

1.8 Checking our work against GPT-2

A tokenizer that disagrees with the published one is not GPT-2’s tokenizer. So we check.

Here is a short sample sentence, one that mixes punctuation, a special token, and a word no vocabulary contains. It is the test sentence used in Sebastian Raschka’s Build a Large Language Model (From Scratch), chapter 2, which makes the result easy to compare if you have the book:

from bpe.tokenizer import Tokenizers


def main() raises:
    var tokenizer = Tokenizers.get[Tokenizers.gpt2]()
    var text = (
        "Hello, do you like tea? <|endoftext|> "
        "In the sunlit terraces of someunknownPlace."
    )
    var ids = tokenizer.encode(text)
    print(ids)

The expected output:

[15496, 11, 466, 345, 588, 8887, 30, 220, 50256, 554, 262, 4252, 18250, 8812, 2114, 286, 617, 34680, 27271, 13]

Three things stand out in this output.

50256 is <|endoftext|>, the last ID in a vocabulary of 50,257. It is a special token: it never comes out of merging, and the pre-tokenizer lists it separately.

220 is a lone space, the one before <|endoftext|>. Spaces normally ride on the front of the next word (" In" is 554), but a space with nothing to attach to is a token of its own.

someunknownPlace, a word no vocabulary has, still encodes. It is three pieces: some, unknown, Place. No <UNK>, no error.

How close is the agreement? Take the-verdict.txt, the 20,479-byte story this chapter uses throughout, and encode all of it twice, once with mbpe and once with the reference tiktoken library, using each library’s plain encode:

Vocabulary Tokens Mismatches
GPT-2 (gpt2) 5,145 0
GPT-4 (cl100k) 4,943 0
GPT-4o (o200k) 4,836 0

The IDs match exactly on all three vocabularies. The counts differ because each vocabulary learned its own merges and so cuts the same text differently. GPT-4o spends the fewest tokens here: a larger vocabulary knows more whole words.

The same strings split differently under each vocabulary. Four short test strings, each verified against tiktoken (spaces shown as ␣, since a bare space inside a code span is invisible):

  don't hello world WÉÉ a。b
GPT-2 don + 't hello + ␣ + ␣world W + É + É a + 。 + b
GPT-4 don + 't hello + ␣ + ␣world W + É + É a + 。 + b
GPT-4o don't hello + ␣ + ␣world W + É + É a + 。 + b

The splits mostly agree; the IDs behind them do not, because each vocabulary numbers its own pieces. don't is the sharpest cell: GPT-2 and GPT-4 both cut it as don + 't (IDs 9099, 470 and 15357, 956), while GPT-4o knows the whole contraction as one token, 91418. Both tables above are the output of pixi run validate.

The next section turns those IDs into training examples.

1.9 From IDs to training examples

The model is trained to predict the next token. So the training data is built from the same list twice, once as it is and once shifted left by one.

Take any run of IDs from the encoded text. Call it ids. The input is ids without its last element. The target is ids without its first. Position by position:

position input (what the model sees) target (what it must predict)
0 ids[0] ids[1]
1 ids[0], ids[1] ids[2]
2 ids[0], ids[1], ids[2] ids[3]

Every position is a small prediction problem, and one list of N+1 IDs provides N of them at once. Chapter 2 turns these lists into tensors and gives each ID a vector, and the library that does it is tenmo.

The next section lists the pitfalls to avoid.

1.10 Pitfalls

Forgetting -I .. Code that does from bpe.tokenizer import ... needs the include path. The test files under mbpe/tests/ need it, as the mbpe README shows. main.mojo at the repository root does not.

Data directory. The Mojo loader reads the MBPE_DATA_DIR environment variable, then falls back to ./data/. Run from the repository root or set the variable.

encode versus encode_ordinary. The first recognizes special tokens in the text. The second treats them as ordinary characters. If you expected one ID for <|endoftext|> and got seven, you called the second.

Specials across save and load. save_tiktoken skips special tokens by design. A tokenizer that loads back without them is behaving correctly.

Wrong pre-tokenizer for the file. Loads fine, round-trips fine, wrong IDs. See the end of “A swappable pre-tokenizer”.

The summary follows.

Summary

Eleven characters in, two integers out. Now you know where those two integers come from, and Chapter 2 turns each of them into a vector.

Exercises

Exercise 1.1. Encode the string "Akwirw ier" with the GPT-2 tokenizer. You should get six IDs: 33901, 86, 343, 86, 220, 959. Decode each one on its own. The first four pieces are Ak, w, ir, w: gibberish, spelled out in the largest pieces the vocabulary has. The last two are a lone space and ier. Then decode the whole list and confirm that you get the original string.

Exercise 1.2. Train simple_bpe and mbpe on the same small corpus. Encode a sentence containing a character that is not in the corpus. Compare the two outputs. Which one can you decode?

Exercise 1.3. Remove the Ġ marker from simple_bpe’s pre-tokenizer and train again. Does encode followed by decode still return the input? Why or why not?

Exercise 1.4. Give simple_bpe a rank table. In _tokenize, replace the loop over every rule with a table from each merge to its rank, and repeatedly merge the lowest-ranked adjacent pair in a word. A rule’s rank is its position in the order it was learned. Confirm you get identical IDs on the test corpus.

Exercise 1.5. Measure the tax. Put a paragraph in a file in a language other than English, then compare how many IDs three vocabularies spend on it:

from bpe.tokenizer import Tokenizers


def main() raises:
    var text = ""
    with open("para.txt", "r") as f:
        text = f.read()
    var gpt2 = Tokenizers.get[Tokenizers.gpt2]()
    print("gpt2", len(gpt2.encode(text)), len(text.codepoints()))
    var cl100k = Tokenizers.get[Tokenizers.cl100k]()
    print("cl100k", len(cl100k.encode(text)), len(text.codepoints()))
    var o200k = Tokenizers.get[Tokenizers.o200k]()
    print("o200k", len(o200k.encode(text)), len(text.codepoints()))

Divide IDs by code points for each. Which language pays the most under GPT-2?

Further reading

In the repositories: