Tokenizers, from algorithms to gigabytes per second

Why tokenization matters more than it looks

A tokenizer is a lossless compressor with a fixed codebook. It maps a byte sequence to a shorter sequence of integers drawn from a vocabulary, and every property of that mapping leaks into the model. The first tradeoff is vocabulary size against sequence length. A larger vocabulary compresses better, so the same document costs fewer positions, which means more context per forward pass and fewer steps per epoch of data. The price is a larger embedding matrix and output projection, a softmax over more classes, and rarer tokens whose embeddings train on fewer examples. Modern vocabularies have drifted upward, from GPT-2's 50,257 to the 100k to 250k range common today, because at large model sizes the embedding table is a small fraction of the parameters while sequence length is a hard budget.

The second issue is fertility, the average number of tokens a word becomes. A tokenizer trained mostly on English gives English text a fertility near one and a half, while text in a script the training mix barely covered can fragment into three or four tokens per word, in the worst case one token per byte. The same nominal context window then holds far less content in one language than another, and the same API price per token buys less. Fertility is a property of the tokenizer, not the model, and it is fixed before pretraining begins, which is why multilingual coverage decisions in the tokenizer training corpus echo through everything downstream.

Third, tokenizer bugs are silent. A model trained on ids from one tokenizer and served with a subtly different one does not crash, it just gets worse. Off-by-one special-token handling, a normalizer that strips characters the training run kept, a byte-fallback path that disagrees on invalid UTF-8, all of these produce valid id sequences that are simply not the distribution the weights expect. Because the failure is a quality regression rather than an exception, it survives code review and ships. The evaluation habits that catch this class of bug, golden-file tests over id sequences and end-to-end perplexity checks on a pinned corpus, are the subject of my data pipelines and evaluation notes.

The newer development is that tokenizer speed became a first-order concern. For years encoding was a rounding error, something done once per dataset by a script nobody profiled. Two things changed. Pretraining corpora crossed the trillion token line, where even 50 MB/s of sustained tokenization means more than a day of single-machine work per pass over the raw text. And data-centric research made re-tokenization routine, every mixing ablation, every filtering threshold change, every deduplication experiment reshuffles which documents enter the corpus, and the pipeline tokenizes the result again. When the tokenizer is the slowest stage, iteration speed on data experiments is capped by it, exactly the way slow compiles cap iteration on code. The derivation of BPE training itself, building a tokenizer from a raw corpus, lives in my language models from scratch notes, this page takes the trained vocabulary as given and asks how encoding works and how it gets fast.

The algorithm families

Greedy merge BPE. Byte pair encoding starts from a base alphabet and repeatedly merges the most frequent adjacent pair into a new symbol, recording each merge in order. Take a tiny corpus of word counts, sing four times, singer three, ring two, ringer once, and in once. Counting adjacent pairs across the corpus, i​n occurs eleven times, more than any other pair, so the first merge creates the symbol in. Recounting, in​g now occurs ten times and wins, giving ing. The third count makes s​ing the winner at seven, giving sing. Training is just this loop run tens of thousands of times. Encoding replays the same list, to encode singer you start from characters, apply merge one to get s​in​g​e​r, merge two to get s​ing​e​r, merge three to get sing​e​r, and no further merge applies, so the token ids are those of sing, e, r. The merge list is the entire model, and encoding is deterministic replay, which is what makes BPE such an attractive target for optimization.

Byte-level BPE. Sennrich's original formulation worked over characters, which leaves the question of what to do with a character outside the alphabet. GPT-2's answer was to make the base alphabet the 256 byte values, so every string, in any script, valid UTF-8 or not, has an encoding and there is no unknown token at all. The awkward detail is that raw bytes include whitespace and control characters that are unpleasant inside merge tables, so GPT-2 maps each byte to a printable stand-in character and runs ordinary BPE over those. The cost is that a rare script may get one token per byte, the fertility problem in its extreme form, but the guarantee of total coverage proved so useful that byte-level BPE is now the default for most frontier models, GPT-2 through GPT-4, Llama 3, Qwen, DeepSeek, and most of their contemporaries.

WordPiece. BERT's tokenizer looks like BPE but merges by a different criterion. Instead of picking the most frequent pair, WordPiece picks the pair that most increases the likelihood of the corpus under a unigram language model over the current vocabulary, which works out to favoring pairs whose joint count is high relative to the product of their individual counts. Frequency rewards common pairs, the likelihood ratio rewards pairs that occur together more than chance predicts, so WordPiece prefers genuinely cohesive units over merely frequent ones. The idea descends from Schuster and Nakajima's segmenter for Japanese and Korean voice search. It ships today in the BERT lineage and its distilled descendants, largely through the Hugging Face stack, whose tokenizer plumbing I walk through in my transformers notes.

Unigram and SentencePiece. The unigram method inverts the direction. Rather than growing a vocabulary by merging, it starts with a large candidate vocabulary and prunes. Each candidate token gets a probability, a segmentation of a sentence is scored as the product of its token probabilities, and training alternates between re-estimating probabilities given the best segmentations and deleting the tokens whose removal least hurts total corpus likelihood. Encoding is then a small dynamic program, Viterbi over token boundaries, rather than merge replay, and the probabilistic view gives you sampled segmentations for free, which is what subword regularization uses as training-time augmentation. SentencePiece is the library that made this practical, treating input as a raw character stream with spaces as ordinary symbols so that no language-specific pre-splitting is needed, and it implements both unigram and BPE. The unigram side ships in T5 and ALBERT, while the SentencePiece BPE side carried Llama 1 and 2 and Mistral before the ecosystem's drift back to byte-level BPE.

Why naive BPE encoding is slow

The textbook encoder is quadratic. Hold the word as a list of symbols, scan it to find the adjacent pair whose merge has the highest priority, merge that one pair, and scan again, because a merge changes its neighbors and may create a better-ranked pair anywhere. Each scan is linear in the current length and the loop runs once per merge, of which there can be nearly as many as symbols, so a pathological input, a long run of one repeated character is the classic case, costs time proportional to the square of its length. Pretokenization keeps ordinary words short enough that this rarely explodes in practice, but any tokenizer exposed to untrusted input without a length guard has an accidental denial-of-service lurking in this loop.

The standard fix is the priority-queue encoder. Represent the symbols as a doubly linked list, push every adjacent pair into a heap keyed by merge rank, and repeatedly pop the best pair, splice the two nodes into one, and push only the two new pairs formed with the left and right neighbors. Stale heap entries, pairs whose nodes were already consumed, are detected and discarded on pop. Every merge now does constant list work and a couple of heap operations, giving O(n log n) for the whole word, and this is essentially what the serious implementations do.

Then you profile a real tokenizer and find that the merge loop is not where the time goes. Before any merging, the input is split into pretokens by a regular expression, the GPT-2 pattern and its descendants, which carve text into word-like runs, number runs, punctuation runs, and leading spaces, with case-insensitive contraction handling and, in newer variants, lookahead so that trailing whitespace groups correctly. Merges then apply only within a pretoken, never across one, which is what keeps words short and the merge loop cheap. The consequence is that every single byte of input flows through the regex engine, while the merge loop touches only the short symbol lists the regex hands it, and on typical prose the pretokenization stage dominates wall time. The pattern's Unicode character classes and lookahead make it expensive to match, and the engine processes input roughly a byte at a time through its state machine. Speeding up the heap in the merge loop attacks the minority of the profile.

Pure Python adds a final multiplier. Every symbol is a boxed object, every pair a tuple allocation, every comparison a dynamic dispatch, and the interpreter overhead swamps the arithmetic, which is why a straightforward Python BPE encoder runs in the hundreds of kilobytes per second while the same algorithm in Rust runs a hundred times faster. And the GIL means one Python process tokenizes on one core no matter how many it owns, unless the implementation drops into native code and releases the lock. This is the backdrop against which the fast tokenizers were built.

The fast-tokenizer landscape

Two libraries define the current baseline. Hugging Face tokenizers is a Rust library with Python bindings that implements the full zoo, BPE, WordPiece, and Unigram, plus the normalizer and pretokenizer pipelines that real model configs need, and it parallelizes batch encoding across threads with Rayon. It is the engine behind the fast tokenizer classes in transformers, and its generality is the point, one library loads essentially any model's tokenizer config. tiktoken is OpenAI's leaner take, byte-level BPE only, a Rust core with a small Python surface, and vocabulary files for the OpenAI model families. It gives up generality for simplicity and is usually the faster of the two on the models it covers.

Both live in the same performance class, tens of megabytes per second per core on typical English prose, with the exact figure swinging by a factor of a few depending on vocabulary, text, and how the call crosses the Python boundary. That class is fine for inference and painful for corpora. At 40 MB/s, a 10 TB raw-text corpus is roughly three days of tokenization per core, tolerable once, costly when every mixing ablation repeats it, and at the petabyte scale of a filtered web crawl it becomes a genuine cluster job that owns a real slice of the preprocessing budget. The obvious question is whether the ceiling is fundamental, and the interesting answer is that it is not, because the dominant cost is a regex engine that examines bytes one at a time, and that is precisely the kind of work wide vector units are good at.

Case study, gigatoken

marcelroed/gigatoken is a Rust tokenization library with Python bindings, MIT licensed, at about 2.6k GitHub stars as I write, whose tagline is language model tokenization at GB/s. It positions itself as a drop-in replacement roughly a thousand times faster than Hugging Face tokenizers, and its project-run benchmarks back the claim on big hardware. On an AMD EPYC 9565 with 144 cores, the README reports 24.53 GB/s on the GPT-2 vocabulary against 24.8 MB/s for Hugging Face tokenizers, a factor of 989, and 36.0 MB/s for tiktoken, a factor of 681. For Phi-4 it reports 24.00 GB/s against 29.9 MB/s, a factor of 801, and for Llama 3, whose larger vocabulary and pattern are heavier, 22.15 GB/s against 48.5 MB/s, a factor of 457. On an Apple M4 Max with 16 cores it reports 8.79 GB/s on GPT-2 against 6.9 MB/s, a factor of 1268. All of these are the project's own numbers, and the comparison points are the competing libraries driven from Python, which matters for interpreting the ratio, as the arithmetic below shows.

The techniques the README describes map one-to-one onto the cost profile from the previous section. The first and biggest is replacing the regex engine with SIMD-vectorized pretokenization, with dedicated AVX-512, AVX2, and NEON paths. The insight is that the GPT-2 style patterns, for all their lookahead syntax, are mostly asking a simple per-byte question, is this byte a letter, a digit, whitespace, or punctuation, and where do runs of one class end. A general regex engine answers that through a state machine that eats a byte per step. A vector unit can load 64 bytes at once under AVX-512, classify all of them in a handful of instructions using shuffle-based lookup tables and compares, and reduce the result to bitmasks whose set bits mark boundary positions. The speedup is not the vector width alone, it is that classification becomes branchless straight-line code, no per-byte branch mispredictions, no state-machine dependency chain, the same trick that lets simdjson parse JSON at gigabytes per second. The general background on SIMD execution, lanes, masks, and why branchless matters, is in my parallel computing notes.

The second technique is a cache from pretokens to their token sequences. Natural language is Zipfian, a small set of pretokens, common words with their leading space, covers the overwhelming majority of occurrences, so after a short warm-up almost every pretoken the splitter emits has been seen before and its BPE result can be copied out of a table instead of recomputed. This is Amdahl's law working in your favor, if the cache hits on a fraction h of pretoken occurrences, the merge loop runs only on the remaining 1 − h, and with h in the high nineties the entire BPE stage nearly vanishes from the profile, leaving pretokenization and memory traffic as the whole cost. The README is candid that this is harder than it sounds, the cache grows quickly and pretoken distributions are very long-tailed, so an unbounded table balloons on diverse corpora, and code or multilingual text drags the hit rate down. A cache that stays small enough to live in fast levels of the memory hierarchy hits fast but misses more, a huge one hits more but every probe is a potential cache miss in the hardware sense, and tuning that balance is real work rather than a footnote.

The third technique is architectural, reading data directly in Rust to minimize Python interaction and thread communication. A tokenizer that receives Python strings pays for object conversion at the boundary and serializes on the interpreter, and a thread pool that ships many small work items through queues pays synchronization per item. Reading files natively lets the library split input into large per-thread chunks, keep each core streaming through its own region with no handoffs, and return one packed result, which is how 144 cores can scale near linearly instead of drowning in coordination. The README also mentions late-stage work on eliminating branches and improving cache behavior, which is what the endgame of this kind of optimization always looks like, the algorithm is settled and the remaining wins are microarchitectural.

It is worth doing the per-core arithmetic honestly, because the thousandfold headline conflates three different wins. 24.53 GB/s across 144 cores is about 170 MB/s per core. Against tiktoken's 36.0 MB/s in the same benchmark, treated as roughly what one saturated core delivers, the per-core algorithmic improvement, SIMD pretokenization plus the pretoken cache, is a factor of about five to seven. The remaining two orders of magnitude come from actually scaling across all 144 cores and from keeping Python, its GIL, and fine-grained thread communication off the hot path entirely. That decomposition does not diminish the result, a five to sevenfold single-core win on mature code is excellent engineering and the scaling is the product's whole point, but it clarifies what you should expect on your own hardware, which is per-core gains times however many cores you can actually feed with data.

Practical surface. Installation is pip install gigatoken. There is a compatibility mode, gt.Tokenizer(...).as_hf() or .as_tiktoken(), that mimics the existing libraries' interfaces for drop-in swaps, and a native API where TextFileSource hands file reading to Rust for maximum throughput. Supported families include GPT-2, Qwen, Llama 3 and 4, DeepSeek, Phi-4, GLM, Nemotron, Gemma, Mistral, and CodeLlama. The limitations are stated plainly in the README, WordPiece is unsupported, SentencePiece paths are much less optimized, Windows testing is minimal with WSL recommended, file sinks are not yet implemented, and iterating results from Python goes through ABI3, which is slow enough that you should keep results in bulk arrays rather than looping over them in the interpreter.

Measuring it on this machine

Project benchmarks deserve replication, so I ran a small one here, an Intel Xeon Platinum 8480+ with 52 cores, all tokenizers using the GPT-2 vocabulary, single process. The corpus is about 103 MB of text produced by stripping this site's own HTML to plain text, roughly 13 MB of prose repeated eight times with small variations, split into documents of about 8 KB. That repetition matters, it is a favorable case for gigatoken's pretoken cache, and even the base text is uniform technical English, so read these as numbers for an easy corpus, not a multilingual crawl. Each configuration timed only the encode call, with token counts computed outside the timer, and all three libraries produced exactly 28,239,407 tokens on the same documents, which is a parity check in itself. These are my measured numbers, not the project's.

The gigatoken figures are medians of three fresh-process runs and were stable to a few percent, though the fastest configurations finish the whole corpus in tens of milliseconds, so treat those as coarse. The shape of the results matches the analysis. With parallelism off, gigatoken ran about 22 times faster than single-threaded tiktoken here, larger than the five to sevenfold per-core estimate above, plausibly because the repetitive corpus keeps the pretoken cache unusually hot. The threaded paths of the incumbent libraries scaled poorly from Python, 52 threads bought tiktoken a factor of three, while gigatoken's native file path reached 2.9 GB/s in one process, about 80 times the best tiktoken configuration and about 160 times the best Hugging Face one on this machine. I did not reproduce a full thousandfold gap here, and on this corpus and core count I would not expect to, but the claim that gigatoken sits two orders of magnitude above the incumbents on corpus work survives contact with local hardware.

Swapping it into an existing pipeline is deliberately boring. The compatibility mode mimics the interface you already call, and the native path is worth the small rewrite wherever the input is files.

import gigatoken as gt

# Before, the Hugging Face path.
from tokenizers import Tokenizer
hf = Tokenizer.from_pretrained("gpt2")
ids = [e.ids for e in hf.encode_batch(docs)]

# After, same call sites, gigatoken underneath.
fast = gt.Tokenizer("gpt2").as_hf()
ids = [e.ids for e in fast.encode_batch(docs)]
# A tiktoken-shaped swap is the same idea.
enc = gt.Tokenizer("gpt2").as_tiktoken()

# For corpus preprocessing, skip Python strings entirely.
tok = gt.Tokenizer("gpt2")
tokens = tok.encode_files(gt.TextFileSource(["shard-000.txt", "shard-001.txt"]))
# One ragged array back. Keep it in bulk form, per-token
# Python iteration goes through ABI3 and is slow.

When speed matters, and checking your swap

Tokenizer throughput matters in three places. Corpus preprocessing, where the tokenizer runs over every byte you own and the difference between 30 MB/s and 3 GB/s is the difference between a cluster job and a coffee break. Data ablations, where each experiment re-tokenizes a new mixture and tokenizer speed multiplies directly into research iteration rate. And streaming ingest, tokenize-on-the-fly training or evaluation loops, where a slow tokenizer starves accelerators exactly the way a slow dataloader does, a failure mode I discuss in PyTorch in the wild. It mostly does not matter at inference, a chat request is a few kilobytes, microseconds of tokenization against tens of milliseconds of model time, and no tokenizer swap will move a latency dashboard. Adopting a fast tokenizer for serving alone is optimizing the wrong term.

When you do adopt one, the thing to verify is exact token-id parity against your reference implementation, because the failure mode is the silent quality bug from the first section. Aggregate token counts matching is encouraging but insufficient, two tokenizers can disagree on segmentation and coincidentally produce similar counts. Check ids elementwise, and weight the test set toward the inputs where implementations historically diverge, whitespace runs and trailing spaces, tabs and CRLF, contractions in mixed case, non-Latin scripts, emoji and combining characters, invalid UTF-8 if your pipeline can see it, long digit runs, empty and whitespace-only strings, and every special token your training setup uses, since special-token splitting is configuration, not vocabulary, and is the most common source of drift. Byte fallback deserves particular attention on SentencePiece-style tokenizers, where unknown characters decompose into byte tokens and implementations have disagreed about edge cases.

import tiktoken
import gigatoken as gt

ref = tiktoken.get_encoding("gpt2")
fast = gt.Tokenizer("gpt2")

cases = [
    "  leading spaces\tand\ttabs\r\nand CRLF",
    "don't Can't WON'T it's",
    "café naïve 中文测试 한국어 русский",
    "emoji \U0001F600\U0001F680 and combining é",
    "digits 1234567890 999999999999999999",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    "trailing spaces   ",
    "", " ", "\n\n\n",
]
# Add a slice of the real corpus, synthetic cases never cover enough.
with open("corpus.txt", encoding="utf-8") as fh:
    text = fh.read(2_000_000)
step = len(text) // 200
cases += [text[i : i + step] for i in range(0, len(text) - step, step)]

for i, s in enumerate(cases):
    a = ref.encode_ordinary(s)
    b = list(fast.encode(s))
    assert a == b, f"mismatch on case {i}: {s[:50]!r}\n{a[:12]} vs {b[:12]}"
print(f"parity ok on {len(cases)} cases")

I ran exactly this check here, 212 cases across the synthetic inputs and corpus slices, comparing gigatoken against both tiktoken and Hugging Face tokenizers on the GPT-2 vocabulary, and got zero mismatches. That is the result you should demand before a fast tokenizer touches a training corpus, and it costs seconds to obtain. Pin the tokenizer version alongside the check, and re-run it in CI, because parity is a property of two specific versions, not of two libraries.

References

1. Sennrich, R., Haddow, B. and Birch, A. (2016). Neural machine translation of rare words with subword units. ACL. arXiv:1508.07909
2. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D. and Sutskever, I. (2019). Language models are unsupervised multitask learners (GPT-2). OpenAI report
3. Kudo, T. and Richardson, J. (2018). SentencePiece, a simple and language independent subword tokenizer and detokenizer for neural text processing. EMNLP demo. arXiv:1808.06226
4. Schuster, M. and Nakajima, K. (2012). Japanese and Korean voice search. ICASSP. The origin of the WordPiece segmenter. Google Research PDF
5. Roed, M. gigatoken, language model tokenization at GB/s. Techniques, benchmarks, and limitations quoted in the case study are from the project README, accessed 2026-07. github.com/marcelroed/gigatoken
6. OpenAI. tiktoken, a fast BPE tokenizer for OpenAI models. github.com/openai/tiktoken
7. Hugging Face. tokenizers, fast state-of-the-art tokenizers in Rust with Python bindings. github.com/huggingface/tokenizers