TokenBpe A editorial on how tokenizers can be sped up.

Introduction

Every LLM pipeline starts with a tokenizer and almost no one thinks about it. The model gets the headlines, the tokenizer is quietly burning microseconds per token per request, forever. If you're serving millions of requests or just training on a corpus that doesn't fit in memory that "quietly" adds up.

This post is a walk through TokenBpe, a BPE tokenizer that I've written from the ground up in C++20. It covers what the various components are, how each one works, what specific techniques give you a performance gain and why. All of this is based on the actual code (include/tokenizer/, src/, utils/) and the benchmark figures are from a properly audited 3 way comparison against OpenAI's tiktoken (Rust) and Hugging Face tokenizers.

Headline numbers (Shakespeare corpus, 1.06 MB, GPT-2 vocabulary, 12 hardware threads, Intel i5-11260H):

~5.2× tiktoken and ~19.9× HF on 12-thread encoding. And ~6.1× scaling from 1 to 12 threads natively. Let's open the hood.

What a BPE tokenizer actually does

BPE encoding has two phases:

1. Pre-tokenisation: split the raw text into word-like pieces ("pre-tokens"). GPT-2's approach is to split on letter runs, digit runs, whitespace runs, contractions (i.e. 's, 're, 'll etc), punctuation runs and to fold the leading space into the next token (so " hello" is one pre-token rather than " " + "hello").
2. Merge based encoding: each pre-token is a sequence of single bytes. You repeatedly find the adjacent pair with the lowest merge rank and replace it with the merged token id, until no more merges can be applied.

Decoding is trivial really: just map each token id to its bytes and concatenate.

The naive implementation of this is fine. The real question is where the time goes and the answer, as ever, is everywhere, a little bit at a time. So TokenBpe attacks every layer:

text ─▶ SWAR pre-tokenizer ─▶ dual-cursor split ─▶ per-thread cache ─▶ linked-list merge ─▶ token ids 

with a persistent thread pool under the whole thing, a flat binary model format and a zero copy NumPy boundary on top.

Component tour

1. The pre-tokenizer: SWAR instead of regex

• The problem is GPT-2's official tokenizer uses a regular expression to split the text. Regex engines are general purpose monsters backtracking, capture groups, Unicode classes all of which are completely unnecessary when you're just trying to determine if a run of bytes is letters or not.

The technique. SWAR (SIMD Within A Register) does the 8 bytes per 64 bit word classification using pure integer arithmetic. No SSE/AVX intrinsics at all, it's all done in the 64 bit ALU.

// swar.hpp (simplified) // All 8 lanes are bytes; HIGH_BITS is OR'd in before subtracting // min so no lane can borrow from its neighbour. bool all_bytes_in_range(uint64_t v, uint8_t min, uint8_t max); bool all_ascii_lower(uint64_t v); // [a-z] bool all_ascii_upper(uint64_t v); // [A-Z] bool all_ascii_letters(uint64_t v); // both, via v | 0x20 bool all_ascii_digits(uint64_t v); // [0-9] bool all_bytes_equal(uint64_t v, uint8_t b); 

The range check is written very carefully indeed: it rejects the high bit bytes first, then ORs in HIGH_BITS prior to subtracting min, so a lane can never borrow from its neighbour. load64 does an unaligned 64-bit load via memcpy which ends up as a single instruction.

The splitter (pre_tokenizer.hpp) then scans:

• letter runs and digit runs 8 bytes at a time, scalar tail;
• space runs 8 bytes at a time with all_bytes_equal;
• contractions's, 't, 'm, 'd, 're, 've, 'll;
• punctuation runs (all other non-alphanumeric/non-space/non-apostrophe characters are grouped)

And crucially next_token() returns a std::string_view into the original buffer. No pre-token is ever materialised as a string. The caller owns the text lifetime, the splitter just points into it.

The speed payoff. Byte classification goes from one branch per byte to one instruction per eight bytes for the majority of the scan. No regex engine is actually invoked at all. The only caveat here is that it's an approximation of GPT-2's regex (exotic Unicode whitespace can have different effects on splitting), which is why the token counts on the Shakespeare corpus differ by ~1.9% from tiktoken. Roundtrips are always exact though.

2. The dual cursor: instruction-level parallelism without threads

The problem. Pre-tokenising left to right is a single dependency chain: scan, emit, scan, emit. The CPU can't get ahead of itself as each step is dependent on where the last one left off.

The technique. dual_cursor.hpp finds a safe split point a space or newline within ±128 bytes of the midpoint, searching backwards first (inputs under 256 bytes aren't split) and runs two LexerCursors alternately in one fused loop:

// dual_cursor.hpp — sketch find_safe_split_boundary(text); // near midpoint, whitespace-aligned LexerCursor a{begin, split}, b{split, end}; while (a.has_more() || b.has_more()) { if (a.has_more()) emit(next_token(a), out_a); if (b.has_more()) emit(next_token(b), out_b); } 

Each cursor's dependency chain is independent so the superscalar core has two instruction streams to work on. Output order is preserved by writing the first half into out_a and the second half into out_b and then concatenating.

What it is NOT: threading. It's a fused, allocation-free iteration that also eschews the need to materialise a std::vectorstd::string_view of pre-tokens.

3. The merge loop: intrusive linked list, no allocations

• The problem is the naive BPE merge is "find the lowest rank adjacent pair, replace it and repeat" and with vectors that's an O(n) erase and shift per merge plus string building for the merged tokens.

The technique. encode_chunk_uncached_to_buffer() (the heart of src/encoder.cpp) represents the pre-token as a thread-local array of nodes:

struct ListNode { TokenId token; int32_t prev; int32_t next; }; 

The algorithm:

1. Reset the thread local scratchpad (g_scratchpad) and lay out one ListNode per byte.
2. Repeat: go through the list once. For every adjacent pair in merge_ranks_, keep the one with the globally lowest rank (not the first one encountered, training order takes priority regardless of position). If none, stop.
3. Splice: overwrite the left node's token with the new id, point its next past the right node and fix the back-pointer. O(1) unlink, zero allocation.**
4. Just go through the list and output the ids.

The speed payoff. No string allocations at all during merging, ever. The merged bytes were already computed by add_merge() when the model was built. The cost is an O(n) scan per merge and for pre-tokens (which are almost always very short) that's a very reasonable trade.

This is also where the TokenPairHash comes in: a splitmix64 style mixer on first << 32 | second, giving us unordered_map lookups that won't pathologically collide.

4. The pre-token cache: 512 KiB of direct-mapped memoization per thread

• The problem is of course that pre-tokens are repeating all the time ("the", "and", common names). Running the merge loop for every instance of that is absolutely wasted work.

The technique. Each thread gets an 8 192-slot, direct-mapped cache:

static_assert(sizeof(CacheSlot) == 64); // exactly one cache line // slot = fnv1a64(word) & 0x1FFF // slot = { hash, word_len, token_count, char word[22], TokenId tokens[8] } 

• Direct-mapped: no probing, no chaining, no eviction policy. One line load plus a memcmp on a hit.
• Collisions just overwrite correctness has nothing to do with a hit so it's all speed.
• Only pre-tokens of 22 bytes or less which produce 8 tokens or less are cached (the short pre-tokens are by far the majority of the real text).
• get() returns a std::span into the slot (zero copy, the ids are just inserted directly into the output).

The speed payoff. A cache hit bypasses the scratchpad, the list construction, the merge scans and the hash-map probes of the pair table it's just a single line lookup and a bulk insert. The 512kib/thread footprint remains in L2 on most cores.

5. Decode: flat table, two passes, one allocation

Decoding looks up decode_table_[id].size() to get the total output size, calls resize() once and then memcpys each token's bytes forward. The table is id-indexed so decode never touches a hash map. Any ids outside the table are silently skipped (a corrupt stream just degrades rather than aborting). Result: 341mb/s, ~2.9x tiktoken, ~13.7x HF.

6. The thread pool: persistent, dynamic, warm

Spawning a thread per batch kills you twice: on thread creation and on cold thread local state. TokenBpe uses a PersistentThreadPool: hardware_concurrency() - 1 workers plus the calling thread, work distributed via a shared atomic cursor (fetch_add) a dynamic schedule with no per-item queue. The workers keep their TokenCache and ThreadScratchpad warm across calls for the life of the process.

Batches go through parallel_tokenize_flat() which returns a single contiguous token array plus a prefix sum offsets array (a FlatBatch) such that chunk i is in tokens[offsets[i] .. offsets[i+1]]. No per-chunk vectors, no copies.

Honest limitation: one shared task slot, non-reentrant, threads parameter is advisory. It's a very simple pool really, does one thing and does it well.

7. The zero-copy boundary: C++ → NumPy without tolist()

The nanobind FFI (in utils/bindings.cpp) is where the vast majority of the "fast" tokenizers just quietly fall apart, they're fast at computing, then they copy everything into Python objects. TokenBpe:

• releases the GIL around every compute phase;
• returns encode_flat / encode_batch_flat as numpy.uint32 ndarrays whose std::vector is moved to the heap and owned by an nb::capsule — ownership transfers to NumPy, no tolist() round-trip;
• will accept a 1-D contiguous uint32 ndarray directly as input to decode, reading in place.

Measured effect: ndarray encode at 239.98 MB/s vs 137.40 MB/s for the equivalent list[list[int]] path 1.75x purely from the boundary.

8. The BPE1 binary format: microsecond loads

save()/load() use a compact, order-independent binary:

Header : magic "BPE1" | version u8 | vocab_size u32 | merge_count u32 Vocabulary : vocab_size × { id u32 | len u32 | bytes[len] } Merges : merge_count × { left u32 | right u32 | rank u32 | result u32 } 

Load validates magic/version, clears all tables and the thread-local cache, then rebuilds byte_to_token_id (from length-1 vocab entries essential for imported GPT-2, whose byte tokens are permuted), merge_ranks_, and the flat decode table. A 50 257-token / 49 992-merge GPT-2 model is ~1.5 MB and loads in microseconds. There's also a trainer (frequency-weighted, recompute-based, deliberately simple) and a Hugging Face importer (convert_hf_to_bpe.py) that reverses GPT-2's byte-to-unicode map.

Why it's fast the short version

Every technique maps to a specific cost it eliminates:

The big lesson: no single trick wins. The speedup is the product of a dozen multiplicative factors, boundary copies, allocations, cache misses, dependency chains, each small, all compounding.

Benchmarking methodology

• Same ~64 KiB newline-aligned chunks for all engines (no mid-word cuts penalizing anyone).
• Same GPT-2 vocabulary for every engine.
• Rust Rayon pinned with RAYON_NUM_THREADS to the C++ pool's thread count.
• Roundtrip verified (decode → compare) for fast_bpe and tiktoken before timing.
• Both fast_bpe boundary types measured (ndarray vs list) so the FFI cost is visible.
• Median of 9 runs after 3 warm-ups; numbers vary ±5% run to run.

fast_bpe (C++20) Encode 12T 239.98 MB/s 74.80 Mtok/s zero-copy ndarray fast_bpe (C++20) Encode 12T 137.40 MB/s 42.83 Mtok/s Python list[list[int]] tiktoken (Rust) Encode 12T 45.83 MB/s 14.56 Mtok/s HF tokenizers Encode 12T 12.08 MB/s 3.84 Mtok/s fast_bpe (C++20) Decode 1T 341.01 MB/s 106.30 Mtok/s zero-copy ndarray 

Native C++ suite: 41.81 MB/s single-threaded → 254.88 MB/s on 12 threads = 6.10× scaling. (Not a perfect 12× memory bandwidth and the single split point in the dual cursor, among other things.)

Caveats to state in the post: the pre-tokenizer is an approximation (~1.9% fewer tokens on this corpus), roundtrips are exact, and fast_bpe vs tiktoken is not a byte-identical id comparison.

Try it out

Build

git clone <https://github.com/Unica2804/Token_BPE.git> && cd BPE_Tokenizer python -m venv .venv && source .venv/bin/activate pip install nanobind numpy # optional, for the 3-way benchmark: pip install tiktoken tokenizers cmake -S . -B build cmake --build build -j ctest --test-dir build --output-on-failure # 10 tests, 52 assertions 

Artifacts in build/: libbpe_core.a, tokenizer_cli, tokenizer_bench, tokenizer_tests, fast_bpe.*.so.

Convert the GPT-2 model (or use the committed gpt2.bpe)

python utils/convert_hf_to_bpe.py \ --vocab gpt2_tokenizer/vocab.json \ --merges gpt2_tokenizer/merges.txt \ --out gpt2.bpe 

Python quickstart

import sys sys.path.append("./build") import fast_bpe enc = fast_bpe.BpeEncoder() enc.load("gpt2.bpe") enc.encode("Hello, world!") # -> list[int] enc.encode_flat("Hello, world!") # -> numpy.uint32 ndarray (zero-copy) tokens, offsets = enc.encode_batch_flat(["line 1", "line 2"]) # chunk i -> tokens[offsets[i]:offsets[i+1]] enc.decode(tokens) # -> str 

Re-run the benchmarks

# MUST run from repo root .venv/bin/python benchmark.py --chunk-kb 64 --warmup 3 --runs 9 ./build/tokenizer_bench 

Takeaways

1. Tokenizers are real software with real performance engineering in them.
2. Profile the boundary you cross most often for Python bindings, that's the FFI, not the algorithm.
3. Allocation-free hot paths (thread-local scratchpads, inline cache slots) beat clever data structures.
4. Measure against independent implementations; "it roundtrips" beats "it matches somewhere".

Built with C++20, nanobind, Catch2. Code, benchmarks, and the audited comparison script are in the repo.