Building a Fast Tokenizer, One Bottleneck at a Time: The Algorithms

01The layer nobody looks at

Every conversation you have with a language model starts with a program you probably don’t care about. Before the model sees a single word of your prompt, something has already broken down that text into pieces and replaced each piece with a number. That program is the tokenizer, and for something so essential, I feel like I have seen surprisingly few people talk about it.

It is easy to see why it gets ignored. It sounds like plumbing. Text goes in, integers come out. But that little translation layer quietly decides a surprising amount. It helps explain why a model that can write you a sonnet may still struggle to count the letters in “strawberry.” It decides why a sentence in some languages costs three times as many tokens and therefore three times the money and consumes three times as much of the context window as the same sentence in English. A tokenizer sits upstream of all of it.

I hadn’t thought much about tokenizers either. Then I watched the first lecture of Stanford’s CS336, which covers tokenization (it's great!) and decided to build one myself. My first version followed that lecture and Andrej Karpathy’s video. It was about a dozen lines, and it worked.

From there, I started reading real-world implementations, including OpenAI’s tiktoken and Hugging Face Tokenizers. That eventually led me to gigatoken. In one published GPT-2 benchmark using 144 cores, it encoded text roughly 1000× as fast as Hugging Face Tokenizers while producing matching output.

Seeing 1000× faster made me assume there had to be one big trick. There wasn’t. There was a chain of smaller ideas, each building a little over the previous and revealing a little more about where the program was spending its time. This series is that journey. We’ll start from zero: what a tokenizer does, why language models need one, and how byte-pair encoding (BPE) learns the pieces it uses. Then we’ll build the simplest version in Python and make it faster one bottleneck at a time. I'm not assuming any prior tokenization knowledge for this series:)

Part 1 stays entirely in Python. By the end, we’ll take the trainer from tens of minutes to under 0.3 seconds. Every implementation optimization is verified merge for merge against its corresponding naive baseline. Part 2 (soon!) picks up when better algorithms are no longer enough and we have to look at the machine itself.

02What a tokenizer actually does

Think from the model’s perspective: what does it actually need? An LLM is basically a giant neural network doing arithmetic on numbers; it does not understand anything else. So, before feeding anything to the model we convert it to a sequence of integers, called token IDs. Those IDs are then placed into a tensor and passed to the model.

That is the tokenizer’s main job.

But... which integers?

We could give every word its own number. English probably has hundreds of thousands of words. The vocabulary is effectively unbounded. Worse, when the model encounters a word that was not present in the vocabulary, there would be no number available to represent it.

At the other extreme, we could give every byte its own number. A byte has eight bits, so there are exactly 2⁸ = 256 possible values. With all 256 bytes in the vocabulary, any UTF-8 text can always be represented.

But now we have the opposite problem. The word the requires three tokens, a paragraph may require thousands, and the model has to learn even the most common words one byte at a time. The vocabulary is tiny, but the sequences become huge. Longer sequences mean more computation, more memory, and less text fitting inside the model’s context window.

The useful answer sits between those two extremes.

Think of the vocabulary as having a fixed number of slots, say 50,000. We reserve 256 of them for individual bytes, so there is always a way to represent any text. We can then use the remaining slots for pieces of text that appear often (so we can represent frequent text with fewer tokens). Each piece gets its own number, just as a whole word or byte would.

If the appears often enough to earn a slot, it costs one token instead of three. A less common word such as discombobulated might become dis + comb + obu + lated. A typo might break into even smaller pieces. If necessary, it can always go all the way down to the individual bytes, which are always available.

This middle ground is called subword tokenization. The vocabulary stays a manageable size, common text takes fewer tokens, and unfamiliar text still works. But, since we have limited slots, which ones should we keep?

A tokenizer therefore has two separate jobs. Training decides which pieces deserve a place in the vocabulary. Encoding uses that vocabulary to turn new text into token IDs. We’ll start with training: how do we choose those pieces?

We want to somehow learn the useful pieces from text itself. One popular way to do that is byte-pair encoding, or BPE.

03Byte-pair encoding

BPE is a compression trick from 1994 which turned out to work well for language models. The best part is that the basic idea takes only a minute to understand.

We start with raw bytes. There are 256 of them (0-255). When we encode text as UTF-8, it becomes a sequence of integers in that range. This means any text can always be represented using our initial vocabulary of 256 bytes.

Now suppose we have some training text.

First, count every pair of adjacent tokens and find the pair that occurs most often. Say it is (b'h', b'e') and that it shows up 20,000 times. We create a new token for it and assign it the next available integer, 256. We then replace each occurrence of h followed by e with this new token.

The sequence becomes roughly 20,000 tokens shorter, and our vocabulary gains one new entry:

256 → b"he"

Perhaps (256, b'l') is now the most common pair. Since token 256 represents he, this pair represents hel. We assign it another new token ID:

257 → b"hel"

We keep going like this for a few thousand rounds and we have a fully grown vocabulary where many common words and word pieces are represented by single token IDs and rare ones can be broken down into pieces. All of this, learned from data. That’s the entire algorithm. Here is a version close to the one I first wrote:

def train(self, text: str, vocab_size: int) -> None:
    ids = list(text.encode("utf-8"))
    for i in range(vocab_size - 256):
        counts = Counter(zip(ids, ids[1:]))     # count adjacent pairs
        pair = max(counts, key=counts.get)      # most frequent one
        new_id = 256 + i
        self.merges[pair] = new_id
        self.vocab[new_id] = self.vocab[pair[0]] + self.vocab[pair[1]]
        ids = _merge(ids, pair, new_id)         # rewrite the whole corpus

A dozen lines, and it works!

It is also, as written, the slowest thing in this post by several orders of magnitude.

04Why the obvious version is slow

A quick word on the numbers before the first one lands:

Now look at the training loop again, stripped to its two expensive lines:

for i in range(vocab_size - 256):
    counts = Counter(zip(ids, ids[1:]))     # full pass over the corpus
    pair = max(counts, key=counts.get)
    ids = _merge(ids, pair, new_id)         # another full pass, new list

We're making two complete passes over the corpus, every merge. One to count pairs, another to replace the winning pair. If the corpus contains n tokens and we perform M merges, the total cost is roughly Θ(M·n). This is because we are scanning almost the entire corpus once again for every merge.

For practical purposes, n stays roughly constant, and every merge costs about what the last one did. You can see it in the timings (on a 400 KB corpus):

Double the merges and the runtime nearly doubles with them. Θ(M·n) behaving like we would expect.

And this only gets worse at realistic vocabulary sizes, where tokenizers may learn tens of thousands of merges.

So the question is: how do we stop paying for the entire corpus on every single merge?

05What must stay the same

Now onto the optimizations! There is just one condition: every faster version must learn exactly the same tokens as the simple one. If the result changes, we have not made BPE faster; we have built a different tokenizer.

That sounds straightforward, but a few details that the simple version skims over can quietly change the result. We need to pin them down before we can trust any speedup.

A tokenizer has two programs, and they are very similar:

• Training looks at the corpus and asks, greedily, "which pair is most common right now?". It runs once, offline and its output is a list of merges.
• Encoding takes that list and asks, for some new string "which of these merges was learned earliest?". It keeps applying it over and over, until it does not apply.

# train  — "which pair is MOST COMMON in the corpus right now?"
pair = max(counts, key=lambda p: (counts[p], -p[0], -p[1]))

# encode — "which pair was learned EARLIEST?"
pair = min((p for p in counts if p in self.merges), key=lambda p: self.merges[p])

Encoding walks on the path that training has already set. It has to replay that in order, because merges are built out of earlier merges. Train on "ab ab ab cd cd cd cd":

rank 256: (' ', 'c')   ->  b' c'
rank 257: (256, 'd')   ->  b' cd'       # built out of 256
rank 258: ('a', 'b')   ->  b'ab'
rank 259: (257, 257)   ->  b' cd cd'    # built out of 257, twice

Later tokens (like 259) cannot exist until 257 does, which itself cannot exist until 256 does. Together, the merges form a dependency graph. A merge’s rank is always higher than the ranks of its two inputs because it was created later. The merge order is therefore already a valid topological ordering of that graph.

Two details matter if we want every version to learn the same vocabulary:

• Ties. If two pairs have the same count, I use a fixed rule: highest count, then lowest token IDs.
• Overlaps. In "aaa", merging (a, a) could use the left pair or the right one. I always take the leftmost pair, matching GPT-2, tiktoken, and HF tokenizers.

These choices look minor, but they change the result. Reversing the overlap order produced a different vocabulary in all 400 random corpora I tested.

06Fix 1: stop rescanning the corpus

Why are we really doing two full passes on every merge? A merge is a local event. Suppose we merge (A, B) in this sequence:

L A B R

The three old pairs around it disappear:

(L, A), (A, B), (B, R)

And two new pairs are created around the merged token X:

(L, X), (X, R)

That is just five local updates: three removals and two additions. Everything else in the corpus stays exactly the same. Recounting every pair from scratch is pure waste.

So let's not do that. Keep information about a pair's count and position with these two structures:

pair_counts:    dict[pair, int]        # how many times each pair occurs
pair_positions: dict[pair, set[int]]   # exactly where

pair_counts tells us how common each pair is while pair_positions tells you exactly where it lives. So when we merge, it allows us to straight away jump to the spots that matter and update only the pairs immediately around the merge.

We need one more thing: a way to pull a token out of the middle of the sequence without shifting everything after it (which would be its own O(n) pass). The answer is a doubly linked list. For every token position i, we store:

nxt[i]      # next live token
prev[i]     # previous live token
alive[i]    # whether this position still exists

We don't really delete/remove anything, we just mark that particular slot dead and relink its neighbours around it.

Does it produce the identical tokenizer? Yes! I verified it merge for merge against the naive trainer. All we've changed is how many times we look, and the payoff looks like this:

10-12× faster, with exactly the same output.

07Fix 2: the heap that made everything slower

I profiled the trainer again. The corpus updates were cheap now, but most of the runtime had moved to this one line:

pair = max(pair_counts, key=lambda p: (pair_counts[p], -p[0], -p[1]))

This is a linear scan over every distinct pair in the corpus, running a Python lambda on each one, just to find the single most common pair. It gets worse as training goes on, a bigger vocabulary means more distinct pairs to scan. At vocab 2048, that one line made 10.7 million lambda calls to perform 1792 merges.

What we need is simple: repeatedly find the largest item in a collection whose values keep changing. That sounds like exactly the job for a heap. So I replaced the linear scan with a max-heap. Python’s heapq is a min-heap and does not support updating entries in place, so the implementation uses lazy deletion: push a new entry whenever a count changes, and discard old entries when they reach the top.

Once again, I verified it merge for merge and this is how it looks now:

Linear scan grows with the vocabulary, more pairs means more scanning. The heap curve becomes almost flat because most of the rewriting happens early. Later merges usually affect very few positions, so adding thousands of them costs surprisingly little.

At vocab 512, heap was a regression. It ran 2.4× slower than the simple scan it was supposed to replace. The two approaches only seem to cross somewhere around vocab 4,000.

The important lesson for me was that the operating point is part of the benchmark. Real tokenizers often learn tens of thousands of merges. I had been testing with only 256. Benchmarks need to run closer to the real world workloads otherwise it will point you the wrong way.

08Most of the work happens early

Not every merge does the same amount of work. One merge might rewrite a single position, while another might rewrite thousands. So instead of counting only the number of merges, I counted how many positions they actually rewrote:

The first 256 merges already do 64% of the rewriting needed to reach a 16,384-token vocabulary. The remaining 15,872 merges do only 36%.

This happens because BPE always handles the most common pairs first, and language is extremely uneven. A small number of patterns appear everywhere, followed by a long tail of patterns that appear only a few times. This is a consequence of Zipf’s law.

We’ll take advantage of that soon. But first, we need to decide what counts as a reusable piece of text.

09Fix 3: Pretokenization (a deliberate change)

Every fix so far changed only how the trainer runs, never what it learns. Each version produced the same merges as the naive one. Pretokenization is different. It deliberately changes the tokenizer’s rules, so it changes the tokens themselves. The promise from What must stay the same still holds, but the baseline moves with it. From here on, every optimization is checked against a naive trainer that uses these same boundaries, not the original byte-level one.

BPE doesn’t know what a word is. It only sees adjacent tokens, so nothing stops it from merging across spaces.

When I trained the byte-level tokenizer on a mix of code and prose, out of 768 learned tokens, 39 crossed a word boundary. One of them was:

' in range('

That token compresses this particular corpus well because the phrase appears often in Python code. But it isn’t a useful piece everywhere else. The tokenizer is memorizing a phrase from its training text instead of learning pieces it can reuse.

The fix is called pretokenization. Before BPE runs, we split the text into small, word-like chunks called pretokens:

"a   dog"  →  ["a", "  ", " dog"]

A pretoken is not a final token. It is just a boundary. BPE still runs normally inside each chunk, but it can never merge across two chunks.

GPT-style tokenizers use a regex to choose those boundaries. You don’t need to understand the full pattern to follow the rest of this post. At a high level, it separates letters, numbers, punctuation, newlines, and whitespace. Two details are worth knowing:

• Spaces often stay attached to the following word. That is why tokens tend to look like " dog" instead of "dog".
• Long numbers are split into groups of at most three digits. 1234567 becomes 123, 456, and 7.

Pretokenization does have a cost. On a 100 KB slice of source code at vocabulary size 1,024, the token count increased from 40,672 to 42,890, about 5%. We give up some compression in exchange for pieces that are more likely to be useful outside the training corpus.

The boundary itself takes very little code. I build the linked list separately inside each pretoken:

for start, end in slices:
    for i in range(start, end - 1):
        nxt[i] = i + 1

The end - 1 is what matters. The last token in one pretoken never points to the first token in the next, so a cross-boundary pair simply doesn’t exist.

More importantly for performance, each pretoken can now be processed independently. And when you look at real text, the same pretokens appear again and again.

10Fix 4: stop doing the same work twice

Everything up to here has chipped away at the same question: how fast can I run BPE? There is a better question hiding underneath it: how often do I have to run it at all?

Look at what’s actually in a corpus. My 1.7 MB test file holds 410,197 pretokens, of which only 17,907 are distinct. The average pretoken appears 23 times, and the top 1,000 account for 76% of all pretoken occurrences. A string containing three spaces appears 2,503 times.

top      1 pretokens cover   2.8% of occurrences
top     10 pretokens cover  16.7%
top    100 pretokens cover  44.1%
top  1,000 pretokens cover  76.2%
top 10,000 pretokens cover  97.6%

6,173 pretokens (34% of unique) appear EXACTLY ONCE

Once you feel that, the encoding fix will be hard to miss. Why tokenize the same string 2,503 times? Tokenize it once and remember the answer.

got = cache.get(chunk)
if got is None:
    got = _fast_encode_chunk(list(chunk.encode()), merges)
    cache[chunk] = got
ids.extend(got)

Five lines made encoding 5 times faster, with identical output and a 91.7% cache hit rate. The merge code now runs on barely 8% of the pretokens.

The same idea works during training.

Instead of storing all 410,197 pretokens, we store the 17,907 unique ones together with their frequencies. If a pretoken appears 500 times, every pair inside it contributes 500 to the global pair counts instead of 1. This is weighted deduplication, and it produces exactly the same merge table from about 4% of the data.

Subword-nmt, the original implementation from 2016 that adapted BPE for subword tokenization, already uses this structure. It stores each unique word once, along with its frequency. When it counts a pair, it adds that frequency instead of 1. A reverse index records which words contain each pair, so only those words need to be updated after a merge. That is weighted deduplication and the incremental counting from Fix 1 working together. So I hadn’t really invented anything. I had just rediscovered the optimizations the original implementation had been using all along.

I expected removing 95.6% of the input to produce one of the largest speedups in the post. Instead, deduplication alone gave me only 1.6×. The reason is that deduplication removes repeated pretokens, but it doesn’t remove the distinct pairs inside them. The max() from Fix 2 still scans almost the same set of pairs after every merge. I had reduced the corpus, but the corpus was no longer the bottleneck.

At this point I had two optimizations that looked disappointing. The heap had made my small benchmark slower, and deduplication had removed almost all the input for a 1.6× gain. I had measured each one separately. Now it's time to try them together!

I benchmarked all four combinations: linear scan or heap, and all pretokens or only the unique ones. Every version learned the same merge table.

Look at the first row. The heap alone more than doubles the training time. Once the input is deduplicated, that same heap helps bring the runtime down to 0.16 seconds. The larger vocabulary is even more surprising. Deduplication alone barely changes the runtime, taking it from 25.05 to 23.73 seconds. With the heap added, it falls to 0.29 seconds. Together, the two fixes are almost 85 times faster.

Each fix makes the other more effective. Deduplication removes repeated positions, but a linear scan still searches through almost the same pairs after every merge. The heap removes the search, but without deduplication it still has to update hundreds of thousands of repeated positions. Each bottleneck was large enough to hide the other improvement.

11Where we ended up

Here are the training results in one place, using the same 1.7 MB corpus and a vocabulary size of 16,384:

The first number is extrapolated because the simple version is too slow to run to completion. The other three are measured. At every size where the simple version was practical, the optimized versions learned the same merge table. The only difference is how much repeated work we ask Python to do.

Encoding is a separate job. The pretoken cache took it from 2 MB/s to 10 MB/s.

I then wanted to know how far the remaining Python loop could go. I removed the regex, warmed the cache, and left it doing only dictionary lookups and list.extend. It processed 200,511 bytes in 2.34 milliseconds, or 86 MB/s. I was already pretty happy and then I checked out gigatoken:

Even one gigatoken core is 13 times faster. At that point, there was very little Python work left to remove. The remaining gap was about how the machine ran that work: memory, branches, cache, and parallelism. That is where Part 2 begins.