Byte-Pair Encoding: How Text Becomes Tokens, One Merge at a Time

Every language model on this blog starts from a list of token IDs. The Residual Stream begins by looking up row $i$ of an embedding matrix. This post is about where $i$ comes from: how a string becomes a list of integers, and why the method most modern LLMs use, byte-level byte-pair encoding (BPE), looks the way it does.

The post builds the tokenizer from scratch in about a hundred lines of Python and runs it. A 16-word corpus is small enough to check every merge by hand. The same code then trains on 2.2 GB of children’s stories, is made fast without changing a single merge, and is compared with OpenAI’s released tokenizers. Every number below is printed by a script in the companion folder or cited from a source.

Table of contents

The problem: a finite vocabulary for infinite text

A language model ends in a softmax (see Cross-Entropy and the Softmax Gradient) over a fixed list of symbols, its vocabulary, and begins by embedding one of them. So text has to be cut into pieces from a finite set, and cutting it is the tokenizer’s whole job. The two obvious ways both fail:

Word-level fails on coverage, character-level on cost. Subword tokenization sits between them: a vocabulary of tens of thousands of pieces, where frequent words are one piece and rare words are several. BPE chooses the pieces from data, by repeatedly gluing together the pair of adjacent pieces that occurs most often.

The idea is older than language models. Philip Gage published it in 1994 as a compression algorithm, which “compresses data by finding the most frequently occurring pairs of adjacent bytes in the data and replacing all instances of the pair with a byte that was not in the original data.” It is still compression at heart: a good BPE vocabulary represents its training text in few tokens. Sennrich, Haddow and Birch adapted it to word segmentation for neural translation in 2016. GPT-2 (Radford et al., 2019) made two changes that most LLM tokenizers since have kept: it works on bytes, and its code splits text with a regex before merging. Both are derived below. (Tokenizers built with SentencePiece, such as Llama 2’s, split differently; Where this leads returns to them.)

Start from bytes, not characters

The first decision is the smallest unit, the one that is never split. Unicode gives every character an integer code point: ord("s") is 115 and ord("牛") is 29,275. Unicode 18.0, released in September 2026, defines 172,808 characters. A vocabulary that started from code points would have over 170,000 entries before the first merge, most of them seen a handful of times. The GPT-2 paper makes the same point with the 2019 count: “a base vocabulary of over 130,000 before any multi-symbol tokens are added.”

So the text is first encoded as UTF-8, a variable-length encoding of code points as bytes. ASCII takes one byte, accented Latin letters two, most CJK characters three, and emoji four. About 99% of websites use it (W3Techs, October 2026).

utf8.py prints these bytes and then encodes every code point UTF-8 can represent, counting how many bytes each takes:

s  U+0073  1 byte: 73           = [115]
é  U+00E9  2 bytes: C3 A9        = [195, 169]
à  U+00E0  2 bytes: C3 A0        = [195, 160]
牛  U+725B  3 bytes: E7 89 9B     = [231, 137, 155]
🙃  U+1F643  4 bytes: F0 9F 99 83  = [240, 159, 153, 131]
'héllo': 5 characters, 6 bytes [104, 195, 169, 108, 108, 111]
'Xin chào': 8 characters, 9 bytes [88, 105, 110, 32, 99, 104, 195, 160, 111]

code points by UTF-8 length: 1 byte: 128, 2 bytes: 1,920, 3 bytes: 61,440, 4 bytes: 1,048,576
total 1,112,064; bytes below 0x80 inside a multi-byte character: 0

All 1,112,064 encodable code points (the 1,114,112 in Unicode’s range, less the 2,048 surrogates) come out as sequences of the same 256 byte values. So the base alphabet has exactly 256 symbols and no string is out of vocabulary: any text in any script, any emoji, even invalid input, is a sequence of integers in $[0, 255]$. The last line checks a property used later. A byte below 0x80 never appears inside a multi-byte character; RFC 3629 puts it as “any octet with such a value can only stand for a US-ASCII character, and nothing else.” The price of bytes is length: a byte is a smaller unit than a character, so sequences start long, and the merges buy that length back.

The base vocabulary is fixed before training:

Token ID $i$ is byte $i$. Each merge adds one entry with the next free ID, so after $m$ merges the vocabulary has $256 + m$ entries, plus any special tokens.

The idea: merge the most frequent pair, repeat

Given a corpus as byte sequences, training is one loop:

1. Count how often each adjacent pair of tokens occurs in the corpus.
2. Take the most frequent pair $(A, B)$.
3. Replace every $A$ followed by $B$ with a new token $AB$, which gets the next free ID.
4. Append the merge $(A, B)$ to an ordered list. Repeat until the vocabulary reaches the requested size.

Two rules make this produce useful pieces.

Merges never cross a pre-token boundary. The corpus is first cut into pre-tokens, roughly words with their leading space, numbers and runs of punctuation, and pairs are counted and merged only inside one. The next section shows what happens without this rule.

Merges are an ordered list, not a set. Encoding replays the merges in the order they were learned, and a different order would tokenize the same text differently. That is why GPT-2’s tokenizer ships as two files, vocab.json and merges.txt.

Step 1: pre-tokenization

Pre-tokenization also saves work. In the CS336 handout’s example, if the word text appears 10 times, the pair t, e can be counted once with weight 10 “instead of looking through the corpus.” So the corpus becomes a frequency table of distinct pre-tokens, and every later step works on that table.

The 2016 BPE split on whitespace and marked each word’s end with a special symbol (</w> in the paper’s code). GPT-2 instead split with a regular expression, defined in its encoder.py. bpe.py uses the same pattern with the contractions grouped, the form from tiktoken pull request 234 that the CS336 handout also uses:

# GPT-2's pre-tokenizer with its contractions grouped (tiktoken pull request 234).
PAT = r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

Full script: bpe.py

The alternatives are tried left to right, and the first that matches wins:

The ? at the start of the letter, digit and punctuation alternatives attaches a space to the word after it, not the one before. "low low" is not two copies of low but low and ␣low, two different pre-tokens. The space is byte 32, an ordinary member of the vocabulary, so no end-of-word marker is needed. Because nearly every word in running English follows a space, the learned vocabulary fills with tokens like ␣the, and the bare the is left for the start of a line. GPT-2’s own tokenizer shows the effect, run through tiktoken:

gpt2 'accomplishment': 3 tokens  ac | compl | ishment

gpt2 ' accomplishment': 1 token  ␣accomplishment

accomplishment with no space before it is three tokens; with the space it is one.

bpe.py turns a corpus into the table in two steps: split out special tokens, then run the regex over each chunk and count each match as a tuple of single bytes.

def to_bytes(s):
    """A string as a tuple of one-byte tokens."""
    return tuple(bytes([b]) for b in s.encode("utf-8"))


def pretokenize(text, specials=()):
    """The corpus as a table: {pre-token as a tuple of bytes: how often it occurs}."""
    counts = Counter()
    for chunk in split_special(text, specials):
        if chunk in specials:  # special tokens take no part in training
            continue
        for m in re.finditer(PAT, chunk):
            counts[to_bytes(m.group())] += 1
    return counts

Full script: bpe.py

The corpus is the example from Sennrich et al., with low five times, lower twice, widest three times and newest six times, written as three lines of running text in bpe.py:

# The example corpus from Sennrich et al. (2016), as running text.
CORPUS = ("low low low low low\n"
          "lower lower widest widest widest\n"
          "newest newest newest newest newest newest\n")

Full script: bpe.py

toy.py runs the pipeline on it and prints every step:

pre-tokens, in order: low ␣low ␣low ␣low ␣low ⏎ lower ␣lower ␣widest ␣widest ␣widest ⏎ newest ␣newest ␣newest ␣newest ␣newest ␣newest ⏎

8 distinct pre-tokens, 19 occurrences
  (␣, n, e, w, e, s, t)    5
  (␣, l, o, w)             4
  (⏎)                      3
  (␣, w, i, d, e, s, t)    3
  (␣, l, o, w, e, r)       1
  (l, o, w)                1
  (l, o, w, e, r)          1
  (n, e, w, e, s, t)       1

Eight distinct pre-tokens, 19 occurrences. The leading-space rule is why it is not low: 5, lower: 2, widest: 3, newest: 6: the low that starts line 1 and the four ␣low after it are different rows. The three newlines are one-byte pre-tokens with no pairs at all, so they never affect a merge. From here on, training reads only this table.

What does the regex prevent? no_regex.py takes the first million characters of TinyStories and runs the same merge loop twice: once on each story as one long byte sequence, and once on the pre-token table.

no pre-tokenizer:  e␣  d␣  th  ␣a  .␣  t␣  y␣  s␣  nd␣  to  er  ed␣  the␣  ,␣  wa  in  he␣  to␣  ␣and␣  ou
GPT-2's regex:     he  ␣t  ␣a  ␣s  ␣w  ␣the  nd  ed  ␣b  ␣to  ␣and  ␣h  ␣T  ␣f  ␣wa  in  it  re  ou  ␣l

With no pre-tokenizer, the first merge is e␣: the last letter of one word glued to the space before the next. Seven of the first ten merges end in a space, and ␣and␣ spans two boundaries. These tokens waste vocabulary on fragments that mean nothing alone. With the regex every merge stays inside a word, and words like ␣the, ␣to and ␣and appear within the first eleven merges. The GPT-2 paper gives a related reason for splitting: BPE had learned “many versions of common words like dog since they occur in many variations such as dog. dog! dog?”, so they “prevent BPE from merging across character categories for any byte sequence,” with “an exception for spaces.”

Step 2: count adjacent pairs

For each row, every adjacent pair of tokens adds the row’s count to that pair’s total:

def count_pairs(counts):
    pairs = Counter()
    for tok, freq in counts.items():
        for pair in zip(tok, tok[1:]):  # adjacent pairs, duplicates kept
            pairs[pair] += freq
    return pairs

Full script: bpe.py

The pairs are taken with duplicates kept. If one pre-token holds a pair twice, as (l, o, w, l, o, w) holds (l, o), it counts twice. On the toy table:

14 distinct adjacent pairs
  (e, s)       9
  (s, t)       9
  (w, e)       8
  (l, o)       7
  (o, w)       7
  (e, w)       6
  (n, e)       6
  (␣, l)       5
  (␣, n)       5
  (␣, w)       3
  (d, e)       3
  (i, d)       3
  (w, i)       3
  (e, r)       2

(␣, n, e, w, e, s, t) with count 5 adds 5 to each of its six pairs, and (e, s) reaches 9 from ␣newest (5), ␣widest (3) and newest (1).

Step 3: the merge loop, one merge at a time

The top of that table is a tie: (e, s) and (s, t) both occur 9 times. Something has to break it, and deterministically, or two runs on the same data could learn different vocabularies. The rule the CS336 handout requires, “preferring the lexicographically greater pair,” is one line:

def train(text, vocab_size, specials=(), on_merge=None):
    counts = pretokenize(text, specials)
    vocab = {i: bytes([i]) for i in range(256)}
    merges = []
    while len(vocab) < vocab_size - len(specials):
        pairs = count_pairs(counts)  # naive: recount everything every round
        if not pairs:
            break
        best = max(pairs, key=lambda p: (pairs[p], p))  # count, then the greater pair
        if on_merge:
            on_merge(pairs, best)
        new = best[0] + best[1]
        merged = Counter()
        for tok, freq in counts.items():
            merged[merge(tok, best, new)] += freq  # two rows can become one
        counts = merged
        merges.append(best)
        vocab[len(vocab)] = new
    for s in specials:  # appended after the last merge
        vocab[len(vocab)] = s.encode("utf-8")
    return vocab, merges

Full script: bpe.py

The key (pairs[p], p) compares counts first and, on a tie, the pairs themselves. Python compares tuples element by element and bytes byte by byte, so (b"s", b"t") > (b"e", b"s") because s (115) is greater than e (101). The rule keeps working once tokens like b"low" exist. Sennrich’s subword-nmt uses the same key, max(stats, key=lambda x: (stats[x], x)), added in 2017 to “make max deterministic”; the paper’s own listing, max(pairs, key=pairs.get), left ties to dictionary order.

The merge itself goes left to right without overlap:

def merge(tok, pair, new):
    """Replace every occurrence of pair in tok, left to right, without overlap."""
    out, i = [], 0
    while i < len(tok):
        if i < len(tok) - 1 and (tok[i], tok[i + 1]) == pair:
            out.append(new)
            i += 2
        else:
            out.append(tok[i])
            i += 1
    return tuple(out)

Full script: bpe.py

Merging (a, a) in (a, a, a) gives (aa, a), not two overlapping merges: the i += 2 skips past both halves of a match.

The vocabulary size is $256 + 8 + 1$, eight merges and one special token, so the loop runs eight times:

 #   id  pairs at the top count         merge         new token  count
 1  256  (e, s) (s, t)                 s + t         st         9
 2  257  (e, st)                       e + st        est        9
 3  258  (l, o) (o, w)                 o + w         ow         7
 4  259  (l, ow)                       l + ow        low        7
 5  260  (e, w) (n, e) (w, est)        w + est       west       6
 6  261  (e, west) (n, e)              n + e         ne         6
 7  262  (ne, west)                    ne + west      newest     6
 8  263  (␣, low) (␣, newest)          ␣ + newest    ␣newest    5

Each merge changes the next round’s counts:

• Merge 1, st. Only the three rows holding (s, t) change: (␣,n,e,w,e,s,t) becomes (␣,n,e,w,e,st), and likewise ␣widest and newest. The other half of the tie, (e, s), disappears, because every e that was followed by s is now followed by st. A new pair (e, st) takes its place with count 9.
• Merge 2, est. (e, st) is now the only pair at 9. The suffix that widest and newest share is a token before either word is.
• Merge 3, ow. The tie between (l, o) and (o, w) at 7 goes to o > l.
• Merge 4, low. (l, ow) is alone at 7. ␣low’s tail is now one token, so (␣, low) enters the table at 5.

Then west, ne and newest take three more merges, and the last attaches the space: ␣newest, the corpus’s most common pre-token, is one token.

The counts descend, 9, 9, 7, 7, 6, 6, 6, 5, and the frequent words collapse before anything rarer is touched. That is the compression objective: a merge of a pair with count $c$ shortens the encoded corpus by $c$ tokens (fewer when occurrences overlap, as in (a, a, a)), so choosing the largest count is greedy compression.

Ties are common, and the tie-break decides real structure. Merge 5 is a three-way tie. Had (e, w) won instead of (w, est), the vocabulary would hold ew instead of west, and newest would be built from different pieces. Neither is more correct, but only a fixed rule is reproducible.

lower never becomes a token. It shares the low stem, but (e, r) only reaches 2. After eight merges, lower is still low + e + r. The vocabulary follows frequency in this corpus, not what looks like a word.

The widget below runs the same algorithm, with the same regex, tie-break and merge, on the first 4,000 characters of any corpus typed into it. Merge next shows which rows change, which pair disappears and which new pair appears.

Typing one ordinary sentence into it shows how quickly the top of the pair table turns into ties once the frequent words are used up.

What training produced

Two things come out of the loop, and encoding needs both:

vocab beyond the bytes: {256: b'st', 257: b'est', 258: b'ow', 259: b'low', 260: b'west', 261: b'ne', 262: b'newest', 263: b' newest', 264: b'<|endoftext|>'}
merges: [(b's', b't'), (b'e', b'st'), (b'o', b'w'), (b'l', b'ow'), (b'w', b'est'), (b'n', b'e'), (b'ne', b'west'), (b' ', b'newest')]

The vocabulary maps IDs to bytes, never to strings, because a token like b'\xc3' (the first byte of é) is not valid text on its own. The merges are a list in creation order, and that order defines the tokenizer: the vocabulary can be rebuilt by replaying the merges, but not the other way round. <|endoftext|> is appended after the last merge, so it gets ID 264 here. The CS336 handout’s own example puts it first, at ID 0; either works as long as training and encoding agree.

Encoding: replay the merges by rank, not by count

Encoding new text has no corpus and no counts. It has the ordered merge list, so each merge gets a rank, its position in the list, and the rule becomes: pre-tokenize with the same regex; in each pre-token, find every adjacent pair that is a learned merge and apply the one with the lowest rank; repeat until no pair is a learned merge.

def encode_word(tok, rank, on_step=None):
    """Apply learned merges to one pre-token, earliest-learned first."""
    while True:
        cands = [p for p in zip(tok, tok[1:]) if p in rank]
        if not cands:
            return tok
        p = min(cands, key=rank.get)  # lowest rank wins; position does not matter
        if on_step:
            on_step(tok, cands, p)
        tok = merge(tok, p, p[0] + p[1])

Full script: bpe.py

Applying the earliest-learned merge first repeats what training did to a pre-token it saw, and does something sensible to one it did not. ␣newest, seen five times in training, goes back to one token in six steps:

encode '␣newest'
  start:  (␣, n, e, w, e, s, t)
  iter 1: (n, e)#5 (s, t)#0                  -> apply rank 0 (s, t)
  iter 2: (n, e)#5 (e, st)#1                 -> apply rank 1 (e, st)
  iter 3: (n, e)#5 (w, est)#4                -> apply rank 4 (w, est)
  iter 4: (n, e)#5                           -> apply rank 5 (n, e)
  iter 5: (ne, west)#6                       -> apply rank 6 (ne, west)
  iter 6: (␣, newest)#7                      -> apply rank 7 (␣, newest)
  result: (␣newest)  ids [263]

In step 1, (n, e) comes first in the word, but (s, t) has the lower rank and goes first. Position in the string does not matter; only rank does.

Now lowest, a word the training never saw:

encode 'lowest'
  start:  (l, o, w, e, s, t)
  iter 1: (o, w)#2 (s, t)#0                  -> apply rank 0 (s, t)
  iter 2: (o, w)#2 (e, st)#1                 -> apply rank 1 (e, st)
  iter 3: (o, w)#2 (w, est)#4                -> apply rank 2 (o, w)
  iter 4: (l, ow)#3                          -> apply rank 3 (l, ow)
  result: (low, est)  ids [259, 257]

lowest comes out as low + est, two meaningful pieces from a vocabulary that never saw the word. Step 3 had a real choice: (w, est) would have made west (rank 4), but (o, w) has rank 2 and goes first, and once w is inside ow, the west merge can no longer apply. An unseen word becomes a few known pieces, never <UNK>.

Two more show the limits:

newer: (ne, w, e, r)  ids [261, 119, 101, 114]

zzqq: (z, z, q, q)  ids [122, 122, 113, 113]

newer takes four tokens, because nothing in this corpus taught it er. zzqq matches no merge and stays four raw bytes. Encoding never fails; unfamiliar text just takes more tokens.

Finally a whole string, with a special token in the middle:

text:  'the lowest widest fox<|endoftext|>newest lower'
split: ['the lowest widest fox', '<|endoftext|>', 'newest lower']
ids:   [116, 104, 101, 32, 259, 257, 32, 119, 105, 100, 257, 32, 102, 111, 120, 264, 262, 32, 259, 101, 114]
tokens: t | h | e | ␣ | low | est | ␣ | w | i | d | est | ␣ | f | o | x | <|endoftext|> | newest | ␣ | low | e | r
46 bytes -> 21 tokens = 2.19 bytes per token
round trip: True

46 bytes become 21 tokens, 2.19 bytes per token. the and fox fall back to single bytes because no learned merge covers th, he, fo or ox: the corpus has no h, f or x, and no merge starts from a bare t. GPT-2’s vocabulary of 50,257 tokens encodes the same six words (without the special token) as six tokens, one per word:

gpt2 'the lowest widest fox newest lower': 6 tokens  the | ␣lowest | ␣widest | ␣fox | ␣newest | ␣lower

Decoding: concatenate bytes, then decode UTF-8

Decoding looks each ID up, joins the bytes and decodes once:

def decode(ids, vocab):
    return b"".join(vocab[i] for i in ids).decode("utf-8", errors="replace")

Full script: bpe.py

The one decision is errors="replace". A model can emit any sequence of IDs, including one that splits a multi-byte character, such as the first two of 🙃’s four bytes. Those bytes are not valid UTF-8, and strict decoding would raise. With replace, the bad bytes become the replacement character U+FFFD (�):

'🙃' -> ids [240, 159, 153, 131] -> '🙃'
first two bytes only [240, 159] -> '�'

When the IDs came from encode, the round trip is exact: the bytes joined back together are the original UTF-8, so decode(encode(text)) == text for every string. The toy example above printed round trip: True, and so do 200 TinyStories stories later in the post.

Special tokens are boundaries, not text

A special token such as <|endoftext|> stands for a marker rather than text; this one marks where one document ends and the next begins. It needs its own ID, so a model can learn to emit it and a sampler can stop on it, but it must never take part in training. If it did, a merge could join it to the start of the next word, and it would no longer encode as one token. bpe.py handles it in three places:

1. Training splits the text around special tokens before pre-tokenizing and drops them (pretokenize above). They add nothing to the counts, no merge crosses them, and they join the vocabulary after the last merge.
2. Encoding makes the same split but keeps the special chunks and maps each straight to its ID, never through the merges. That is the split: line in the example above.
3. Reading a large file in parallel cuts it only at special tokens, as the section after next shows.

The split needs care in two places:

def split_special(text, specials):
    """Split text around special tokens, keeping them as their own chunks."""
    if not specials:  # re.split("()", text) would cut between every character
        return [text]
    longest_first = sorted(specials, key=len, reverse=True)
    return re.split("(" + "|".join(re.escape(s) for s in longest_first) + ")", text)

Full script: bpe.py

The tokens are sorted longest first, because regex alternation takes the first alternative that matches: if one special token were a prefix of another, the short one would match part of the long one. They are passed through re.escape, since | is itself a regex character. And with no special tokens at all, the pattern would be (), which matches the empty string at every position and would cut the text between every pair of characters, so the function returns early.

Writing it to disk: why the vocab file is full of Ġ

Tokens are bytes, and neither JSON nor a line of merges.txt can carry arbitrary bytes: a space would break the line’s split, a newline would end the line, and bytes 128 to 255 are not valid UTF-8 on their own. GPT-2’s encoder.py solves this with a fixed table from the 256 byte values to 256 printable characters:

def bytes_to_unicode():
    """GPT-2's table from the 256 byte values to 256 printable characters."""
    keep = (list(range(ord("!"), ord("~") + 1)) + list(range(ord("¡"), ord("¬") + 1))
            + list(range(ord("®"), ord("ÿ") + 1)))  # printable: map to themselves
    table, n = {}, 0
    for b in range(256):
        if b in keep:
            table[b] = chr(b)
        else:
            table[b] = chr(256 + n)  # the rest move past Latin-1, in order
            n += 1
    return table

Full script: files.py

Bytes that are already printable characters keep their own; the rest move, in order, to code points from 256 up. files.py saves the toy tokenizer this way and loads it back:

bytes kept as themselves: 188, moved: 68
space -> Ġ  newline -> Ċ  byte 0 -> Ā

toy_vocab.json, beyond the bytes: {'st': 256, 'est': 257, 'ow': 258, 'low': 259, 'west': 260, 'ne': 261, 'newest': 262, 'Ġnewest': 263, '<|endoftext|>': 264}
toy_merges.txt:
s t
e st
o w
l ow
w est
n e
ne west
Ġ newest

load(save(...)) gives back the same tokenizer: True

That is why GPT-2-family vocabulary files are full of Ġ: it is byte 32, the leading space that pre-tokenization attached to almost every word. The table belongs to the file format. It is applied when saving and undone when loading, and the tokenizer itself never sees those characters.

Making it fast without changing the answer

bpe.py’s train recounts every pair in the table on every merge. That is correct, and it is the version to read, but each merge costs a pass over the whole table, and a real run makes nearly 10,000 merges over tens of thousands of distinct pre-tokens. fast_bpe.py makes three changes, and check.py confirms that none changes the output:

first 500,000 characters, 500 merges: indexed == naive: True, heap == naive: True
whole valid file, pre-token tables at 1, 2, 4, 8 workers identical: True (13,111 distinct pre-tokens)
whole valid file, 10,000-token vocabulary: heap == scan: True

Update only the rows that hold the pair

A merge of (A, B) changes pair counts only in rows that contained (A, B). So the trainer keeps two indexes, built once: pairs, each pair’s total, and where, the rows that hold each pair. One merge then visits only those rows, subtracts their old pairs, merges and adds the new pairs back:

        new = best[0] + best[1]
        changed = set()
        for i in list(where[best]):  # copy: the loop edits these sets
            w, f = words[i], freqs[i]
            for p in zip(w, w[1:]):
                pairs[p] -= f
                changed.add(p)
            w = list(merge(w, best, new))
            for p in zip(w, w[1:]):
                pairs[p] += f
                where[p].add(i)
                changed.add(p)
            words[i] = w
        for p in changed:
            if pairs[p] <= 0:
                del pairs[p]
            elif use_heap:
                heapq.heappush(heap, (-pairs[p], Desc(p), p))
        del where[best]

Full script: fast_bpe.py

The rows to visit are copied to a list first, because the loop adds to those same sets. A row can stay in where after it stops holding a pair; visiting it does no harm, since subtracting and adding back its unchanged pairs nets to zero.

That leaves picking the pair. A max over all pairs is a scan of every distinct pair on every merge. A heap keeps the largest at the top instead: each count that changes is pushed again, and a popped entry whose count no longer matches is skipped (lazy deletion). The heap needs the same tie-break, so Desc reverses the pair comparison, and Python’s min-heap then pops the greatest pair first.

Read in parallel, cutting only at special tokens

Pre-tokenizing is independent for each document, so the file is split into byte ranges, one per worker. A cut at an arbitrary offset could land in the middle of a word, splitting one pre-token into two and changing the counts, or in the middle of a UTF-8 character, leaving a chunk that cannot be decoded. So each cut moves forward to the next <|endoftext|>:

def boundaries(path, n, special=b"<|endoftext|>"):
    """n roughly equal byte ranges, each moved forward to start at a special token."""
    size = os.path.getsize(path)
    cuts = [size * i // n for i in range(n)] + [size]
    with open(path, "rb") as f:
        for i in range(1, n):
            pos = cuts[i]
            while True:
                f.seek(pos)
                data = f.read(1 << 20)
                j = data.find(special)
                if j >= 0:
                    cuts[i] = pos + j
                    break
                if len(data) < 1 << 20:  # reached the end of the file
                    cuts[i] = size
                    break
                pos += len(data) - len(special)  # a token may straddle two reads
    return sorted(set(cuts))

Full script: fast_bpe.py

Every chunk after the first then starts at a special token. The token is ASCII, and ASCII bytes never occur inside a multi-byte character, so each chunk begins on a whole character and can be decoded strictly: a bad cut would raise rather than silently corrupt text. Each worker returns its Counter of pre-tokens, and the main process adds them up.

Where the time goes

tinystories.py trains a 10,000-token vocabulary on the 22 MB validation file and on the 2.2 GB training file, both with a scan and with a heap, on an Apple M4 with 8 workers and nothing else running, one run each:

TinyStoriesV2-GPT4-train.txt: 2,227,753,162 bytes; 8 workers; arm64, 10 cores, Python 3.12.13
pre-tokenize:   85.5 s  (59,933 distinct pre-tokens, 536,592,168 in all)
scan: pick the pair   24.7 s, apply the merge   1.3 s; with pre-tokenizing  111.5 s (pre-tokenize 77%, pick 22%, apply 1%)
heap: pick the pair    0.5 s, apply the merge   2.2 s; with pre-tokenizing   88.2 s (pre-tokenize 97%, pick 1%, apply 2%)
9,743 merges; vocabulary 10,000; <|endoftext|> is ID 9,999
peak memory: 161 MB in the main process, 769 MB in the largest worker

TinyStoriesV2-GPT4-valid.txt: 22,502,601 bytes; 8 workers; arm64, 10 cores, Python 3.12.13
pre-tokenize:    0.8 s  (13,111 distinct pre-tokens, 5,419,001 in all)
scan: pick the pair    6.0 s, apply the merge   0.3 s; with pre-tokenizing    7.1 s (pre-tokenize 12%, pick 84%, apply 4%)
heap: pick the pair    0.1 s, apply the merge   0.3 s; with pre-tokenizing    1.3 s (pre-tokenize 66%, pick 10%, apply 24%)
9,743 merges; vocabulary 10,000; <|endoftext|> is ID 9,999
peak memory: 77 MB in the main process, 58 MB in the largest worker

The two corpora have different bottlenecks. The scan’s cost is the number of distinct pairs times the number of merges, and those grow with the vocabulary and the variety of the text, not with its size. The validation file has 13,111 distinct pre-tokens, the training file 59,933, while the training file has 99 times as many pre-tokens in all. So on 22 MB the scan is 84% of the time, and on 2.2 GB pre-tokenizing is 77%. The heap cuts picking from 24.7 s to 0.5 s on the large file; what remains is almost all pre-tokenizing: reading, decoding, regex matching and combining the workers’ counts. Pre-tokenizing and the merge loop together take 88.2 s, inside the CS336 handout’s hint of “under 2 minutes.”

Memory stays small because training works on the table, not the text: 161 MB in the main process (the script’s MB are mebibytes). Each worker’s chunk is about 266 MiB, a third of its 769 MB peak; the rest is the chunk’s copies while it is decoded and split, and the worker’s counts. More, smaller chunks would lower it.

What 2.2 GB of stories teaches

TinyStories (Eldan and Li, 2023) is a set of short stories written by language models in words “that a typical 3 to 4-year-olds usually understand.” The version 2 training file holds stories written by GPT-4, separated by 2,717,699 <|endoftext|> markers. analyze.py reads the tokenizer trained on it and encodes 200 stories from the validation file, which training never saw:

200 held-out stories, 156,695 bytes
  this tokenizer (10,000):  38,337 tokens, 4.09 bytes per token
  GPT-2's (50,257):         38,775 tokens, 4.04 bytes per token
  round trip exact: 200 of 200

first 12 merges: ␣t  he  ␣a  ␣s  ␣w  nd  ␣the  ed  ␣b  ␣to  ␣and  ␣h
ten longest tokens: ␣accomplishment, ␣disappointment, ␣responsibility, ␣Unfortunately, ␣compassionate, ␣congratulated, ␣determination, ␣encouragement, ␣extraordinary, ␣granddaughter
7,277 of 9,743 learned tokens start with a space (75%)
learned tokens by length in bytes: 2: 360, 3: 912, 4: 1450, 5: 1835, 6: 1666, 7: 1264, 8: 1030, 9: 602, 10: 328, 11: 178, 12: 78, 13: 26, 14: 11, 15: 3

'Once upon a time, there was a little boat.'
  this tokenizer: Once | ␣upon | ␣a | ␣time | , | ␣there | ␣was | ␣a | ␣little | ␣boat | .
  GPT-2:          Once | ␣upon | ␣a | ␣time | , | ␣there | ␣was | ␣a | ␣little | ␣boat | .

trained on 1% of the data (the 22 MB validation file): 8,825 of 10,000 vocabulary entries shared
merge lists first differ at merge 6: n + d (full data) vs ␣t + he (1%)

The first twelve merges come from frequency alone, and they are already English: ␣t, he, ␣a, ␣the, ␣and. The ten longest tokens are whole words with their leading space, from ␣accomplishment to ␣granddaughter. TinyStories has a small vocabulary: the training file holds 59,933 distinct pre-tokens, most of them rare, so BPE spends its 10,000 slots making the common ones single tokens. At 4.09 bytes per token, an average token is about a short word with its space; the example sentence is one token per word, the same split GPT-2’s tokenizer makes.

Two comparisons put the numbers in context.

Against GPT-2’s tokenizer. On the same 200 held-out stories, the 10,000 tokens trained on TinyStories give 4.09 bytes per token and GPT-2’s 50,257 give 4.04. A vocabulary five times larger does slightly worse here, because GPT-2 spent most of it on web text these stories never use. A tokenizer is as good as the match between its training text and the text it meets.

Against 1% of the data. Training on the 22 MB validation file instead of the 2.2 GB training file takes 1.3 seconds instead of 88, and the two vocabularies share 8,825 of 10,000 entries. Their merge lists differ from merge 6: the full data merges n + d there, the small file ␣t + he. Greedy choice turns small differences in counts into different early merges, yet the two vocabularies end up mostly the same. That suggests a way to work: debug on the small file, train once on the large one.

What a tokenizer costs Vietnamese

A vocabulary comes from its training text, and every language that text under-represents pays for it. languages.py counts 2,000 sentence pairs from the OPUS-100 English-Vietnamese test set with OpenAI’s three released vocabularies and with the TinyStories tokenizer:

2,000 sentence pairs
            characters  UTF-8 bytes    words
English         80,240       80,282   15,183
Vietnamese      77,721      100,460   17,437

tokenizer     English bytes/tok  Vietnamese bytes/tok  Vietnamese / English
gpt2           22,689      3.54      66,891      1.50                 2.95x
cl100k_base    20,756      3.87      39,686      2.53                 1.91x
o200k_base     19,947      4.02      25,470      3.94                 1.28x
TinyStories    25,938      3.10      76,892      1.31                 2.96x

• Vietnamese is longer in bytes before any tokenizer runs. The same sentences take 100,460 UTF-8 bytes against 80,282, because letters with diacritics (ă, ơ, ư, ệ) take two or three bytes each.
• GPT-2’s vocabulary charges Vietnamese 2.95 times the tokens. Its merges were learned on mostly English web text, so English words are single tokens while Vietnamese syllables break into pieces: 1.50 bytes per token against 3.54. The TinyStories tokenizer, which saw no Vietnamese at all, does about as badly: 2.96 times.
• Larger, more multilingual vocabularies close most of the gap. cl100k_base (GPT-4) brings the ratio to 1.91 and o200k_base (GPT-4o and later OpenAI models) to 1.28, where both languages get about 4 bytes per token and what remains is mostly the extra bytes Vietnamese starts with.

One phrase shows the mechanism:

'Xin chào thế giới': 17 characters, 22 bytes
  gpt2         15 tokens  X | in | ␣ch | à | o | ␣th | <E1> | <BA> | <BF> | ␣g | i | <E1> | <BB> | <9B> | i
  cl100k_base   9 tokens  X | in | ␣ch | à | o | ␣th | ế | ␣gi | ới
  o200k_base    5 tokens  Xin | ␣ch | ào | ␣thế | ␣giới

GPT-2 keeps à as one token but has no token for ế or ớ, so each falls apart into its three raw bytes. cl100k_base has those letters; o200k_base has whole syllables, ␣thế and ␣giới. The algorithm is the same in all three. Only the training data and the vocabulary size changed.

Everything downstream is priced in tokens: the context window, attention’s cost, the KV cache and a hosted model’s bill. On these sentences, GPT-2’s tokenizer makes Vietnamese cost about three times as much as English, and o200k_base about a quarter more. What “Generative” Means shows the other side of the same fact: a model’s loss per token depends on the tokenizer, so models are compared per byte.

Where this leads

• Other subword algorithms. WordPiece (BERT) picks merges by a score rather than a raw count. Hugging Face’s reconstruction, since “Google never open-sourced its implementation of the training algorithm,” divides a pair’s count by the product of its parts’ counts. The Unigram model (Kudo, 2018) starts from a large vocabulary and repeatedly drops the pieces whose removal costs the least likelihood. SentencePiece implements both BPE and Unigram on raw text, treating whitespace as an ordinary symbol written ▁; tokenizers built on it, such as Llama 2’s, split on whitespace and fall back to bytes only for characters they lack.
• Tokenizer quirks. GPT-2’s \p{N}+ lets the merges decide how digits group, so 12345678 is 123 | 45 | 678. cl100k_base and o200k_base cap digit runs at three, giving 123 | 456 | 78 (tiktoken_compare.py prints both). Whitespace runs, code indentation and capitalization produce similar surprises, and they shape what a model finds easy.
• No tokenizer at all. ByT5 (Xue et al., 2022) feeds raw UTF-8 bytes to the model with a vocabulary of 256, so nothing is learned and no language pays more than its byte length. Sequences get about four times longer than with a SentencePiece vocabulary, and length is exactly what attention is expensive in.
• What the model does with the IDs: the embedding lookup, the residual stream and attention are where The Residual Stream picks up.
• Choosing the tokens for a model. Build a Tiny GPT, End to End, and Train It on This Blog trains its model on this blog with characters or with byte-level BPE tokens, and makes that choice on a dev slice.

Takeaways

• A tokenizer maps unbounded text onto a finite vocabulary. Words fail on coverage and characters on cost; BPE learns a subword vocabulary from data by repeatedly merging the most frequent adjacent pair.
• UTF-8 bytes make the base alphabet exactly 256 symbols. All 1,112,064 encodable code points are spelled with them, so every string encodes and every encoding decodes back exactly.
• Pre-tokenization sets boundaries merges never cross, attaches each space to the following word, and turns the corpus into a weighted table that training reads once. Without it, the first merge on a million characters of TinyStories is e␣.
• Training picks pairs by count, breaking ties toward the lexicographically greater pair. Encoding replays merges by rank, so an unseen word breaks into known pieces instead of <UNK>.
• Special tokens are boundaries: split out before counting, appended after the last merge, mapped straight to their ID when encoding.
• An index of which rows hold each pair, a heap and parallel reading cut at special tokens leave every merge unchanged. On 2.2 GB, pre-tokenizing and merging take 88 s, nearly all of it pre-tokenizing.
• A vocabulary reflects its corpus. Ten thousand tokens trained on TinyStories compress those stories slightly better than GPT-2’s 50,257, 1% of the data gives 88% of the same vocabulary, and a language the data lacked costs about three times the tokens.

References

Start with Karpathy’s minbpe for a second small implementation to compare against bpe.py, then section 2.2 of the GPT-2 paper and its encoder.py. Sennrich et al. is the paper that brought BPE to neural models.

• Gage, A New Algorithm for Data Compression, The C Users Journal, 1994: BPE as a compression algorithm, the origin of the idea. The link is Leon Derczynski’s 2020 reconstruction of the article as a PDF.
• Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units, ACL 2016: BPE for word segmentation, and the low, lower, newest, widest example. Their subword-nmt code is where the (count, pair) tie-break was added in 2017.
• Radford et al., Language Models are Unsupervised Multitask Learners, 2019: the GPT-2 paper; section 2.2 argues for byte-level BPE and against merging across character categories.
• OpenAI, gpt-2/src/encoder.py: the pre-tokenizer regex and the byte-to-character table, which the paper does not describe.
• OpenAI, tiktoken, version 0.14.0: the gpt2, cl100k_base and o200k_base vocabularies used for the comparisons, and their regexes in tiktoken_ext/openai_public.py.
• Karpathy, minbpe: minimal, readable BPE code with a GPT-4-style tokenizer.
• Stanford CS336, Assignment 1: Basics, version 26.0.3: section 2 specifies the byte-level BPE trained here, its tie-break and the TinyStories target.
• Eldan and Li, TinyStories, 2023, and the dataset: the stories the tokenizer was trained on.
• Zhang et al., Improving Massively Multilingual Neural Machine Translation and Zero-Shot Translation, ACL 2020, and the OPUS-100 dataset: the English-Vietnamese sentence pairs. The dataset card does not state a license.
• Wang, Cho and Gu, Neural Machine Translation with Byte-Level Subwords, AAAI 2020: byte-level BPE studied on its own.
• Kudo, Subword Regularization, 2018, and Kudo and Richardson, SentencePiece, 2018: the Unigram model and the library that implements it and BPE.
• Xue et al., ByT5, TACL 2022: a model that reads raw bytes with no tokenizer.
• RFC 3629, UTF-8, and Unicode 18.0: the encoding and the character count.
• W3Techs, Usage statistics of character encodings for websites, October 2026: the share of websites that use UTF-8.