Gigatoken: making tokenisation care about the hardware

The AI industry pours engineering effort into GPU kernels and treats CPU preprocessing as an afterthought. Gigatoken shows how much performance that neglect can leave on the table.

In my first Gigatoken post, I tested its 1,000x claim against my tokeniser workload. On that workload, the tokeniser core ran 30x to 40x faster, including 37.6x on a million-token request split into 1,024 segments. The result was well below 1,000x. I wanted to understand where the gain came from.

I followed the path Gigatoken optimises most aggressively: tokenisers that apply BPE (byte pair encoding) to UTF-8 bytes, including GPT-2 and the tiktoken family. This is the path behind its headline throughput and the one exercised by my benchmark. The project has no technical paper yet, so what follows is my interpretation of Marcel Rød’s source comments, optimisation diary, profiling reports and commit history.Sources: the Gigatoken revision benchmarked and its profiling campaign. Gigatoken describes SentencePiece as less optimised and does not support WordPiece.Gigatoken's README says its optimised path is BPE; SentencePiece is less optimised and WordPiece unsupported.

How BPE turns bytes into tokens

The tokenisers in this article turn UTF-8 text into a sequence of integers. Their vocabularies map byte sequences to token IDs. A token might represent a whole word, part of a word, punctuation or a single byte.

Encoding runs as a pipeline. Pretokenisation is the coarse split immediately before BPE: it divides the continuous byte stream into spans using model-specific rules, commonly expressed as a regular expression. Each intermediate span is a pretoken, which BPE consumes to produce the final model tokens. For GPT-2’s r50k tokeniser:

" Gigatoken optimises pretokenisation for CPU microarchitectures."
→ [" Gigatoken", " optimises", " pretokenisation", " for", " CPU", " microarchitectures", "."]

BPE turns those seven regex spans into fifteen GPT-2 model tokens. The distinction matters because one pretoken can produce several model tokens.

The hard boundaries also explain why the spans are independent. BPE is forbidden to merge across them, so a merge inside one pretoken cannot create or remove a candidate pair in another. The encoder can process each pretoken separately, then concatenate their token IDs in the original order.

Inside one pretoken, BPE starts from bytes or initial symbols. Its merge table was learned when the tokeniser was trained and is fixed during encoding. Each legal adjacent pair has a numeric rank, and the lower rank wins. For the microarchitectures pretoken, one of the later steps merges [it] [ect] into [itect]; the final GPT-2 pieces are [ micro] [arch] [itect] [ures]. The encoder looks up the affected neighbouring pairs again after every merge, chooses the next best candidate and repeats until no legal merge remains. The surviving symbols map to token IDs.See the original BPE-for-subwords paper and OpenAI's compact educational implementation.

What Gigatoken changes inside the Rust core

Traditional Python tokeniser APIs inspect Python input objects and assemble Python-facing results; Gigatoken can read borrowed byte buffers and assemble a flat token buffer in Rust. The service I benchmarked already uses a Rust tokeniser core, so I exclude those API-boundary gains and examine the CPU and memory work inside tokenisation.Moving corpus splitting across the Python/Rust boundary was 11% to 16% faster with identical token IDs. This result covers input handling alone. Output materialisation and the full native-versus-compatibility gap remain unmeasured.

I group the Rust-core changes into four families: 64-byte boundary classification, cached pretoken encodings, compact pair-rank tables for misses and parallel work split at safe pretoken boundaries. These are the four main hot-path changes for the BPE tokenisers in scope. The available measurements use different machines, cache states and controls, which prevents a clean apportionment of the overall speed-up. Each result needs its own baseline.

1. Pretokenise 64 bytes at a time

A general-purpose regex engine finds one matching span after another. Gigatoken’s mask scanner asks which positions in a 64-byte input block begin pretokens. The block sets the scanner’s working width. Pretokens can continue across its edges.

The first classification pass handles ASCII, where one byte represents one character and simple byte comparisons can identify letters, digits, spaces, newlines, apostrophes and other categories. SIMD performs these comparisons across several byte positions at once. Each position is called a lane, and each lane holds one byte here. Four 16-byte NEON loads cover the batch on ARM, two 32-byte AVX2 loads cover it on x86, and AVX-512 can load all 64 bytes at once. The comparisons become separate 64-bit class masks, with one bit for each input byte. Bytes at or above 0x80 go to a second Unicode pass.Source: the mask-scanner architecture and SIMD front ends.

Gigatoken’s loader recognises a fixed set of tokeniser patterns and selects dedicated Rust code for each one. For each mask-scanner family, the implementation expresses the regex’s boundary rules as operations over the class masks. The code treats each mask as a row of 64 on/off positions. A shift slides one row left or right so each byte lines up with its neighbour. AND keeps positions where two conditions are true, OR combines alternatives, and NOT selects positions outside a class. SIMD has finished once it creates the masks; ordinary 64-bit integer operations then combine them into boundary bits.

The author’s detailed optimisation notes and isolated scanner measurements use GPT-2’s r50k pretokeniser, so I use the same worked example here.The r50k module notes document the scalar path and isolated scanner setup. Its 64 ASCII bytes fill one complete scanner block. Under r50k’s rules, a leading space can join the letter, number or punctuation run after it. Shifting the class masks supplies the previous-position relationship for every byte at once. The boundary rules mark starts at byte offsets 0, 10, 20, 36, 40, 44 and 63, producing ·Gigatoken, ·optimises, ·pretokenisation, ·for, ·CPU, ·microarchitectures and .; here · represents a space byte.

Bit-parallel regex evaluation and SIMD block classification predate Gigatoken. Its contribution is specialising those techniques for the fixed patterns used by model tokenisers.The techniques predate Gigatoken: see bit-parallel regex matching and simdjson's SIMD classification. Gigatoken specialises them for tokeniser patterns.

The mask scanner must reproduce the regex’s boundaries. A pretoken can cross a 64-byte edge, so the scanner carries information from the preceding character and looks beyond the right edge where a rule needs it. Each batch returns the starts it can prove. Gigatoken calls any uncertain stretch a bad zone and re-derives its boundaries exactly. Invalid UTF-8 can create a bad zone, as can ordinary text whose boundary conditions remain ambiguous at the edge of a block.

Differential tests compare the combined mask and fallback output with the reference across crafted edge cases, 4,000 generated inputs and OpenWebText samples.The r50k module includes edge-case, fuzz and OpenWebText differential tests.

Unicode stays exact

About 21% of batches in OpenWebText, a web-text corpus, contain at least one non-ASCII byte. UTF-8 breaks the ASCII pass’s one-byte-per-character assumption: one character can occupy several bytes, and those individual bytes do not reveal whether the character is a letter, number or whitespace. The SIMD pass therefore records their positions in a non-ASCII-byte mask for a second classification pass.

The second pass completes the same 64-position masks. For this r50k path, Gigatoken finds each UTF-8 lead byte, decodes its code point and uses a packed table of about 272 KiB to classify the character as a letter, number, whitespace or other. It stamps that class across every byte of the UTF-8 character, preventing a continuation byte from becoming a false boundary, then adds those results to the masks used by the tokeniser’s boundary rules.

Any region the masks cannot settle falls back to Gigatoken’s scalar walker. The walker uses ordinary integer instructions and advances one span boundary at a time. It also handles CPUs without the required SIMD features, the incomplete tail of a buffer and bad zones such as invalid UTF-8 or ambiguous batch-edge cases. For r50k on the OpenWebText sample, about 0.4% of batches require scalar re-derivation.See Gigatoken's packed Unicode tables and r50k scalar fallback.

When boundaries are requested one at a time, the scanner finds the lowest set bit with trailing_zeros and clears it with mask &= mask - 1.mask &= mask - 1 clears the lowest set bit; trailing_zeros finds its position first. For example, 1011000 & 1010111 = 1010000. The hot encode path converts each mask into a flat buffer of boundary offsets, collects up to 256 spans, then processes them in a counted loop. The counted loop reduces data-dependent control flow in boundary discovery and consumption. Cache probes, BPE misses and token emission still carry their own branches and dependent work.

On GPT-2/r50k over a 1 GB OpenWebText sample, the mask scanner reached 2,460 to 2,600 MB/s against 983 MB/s for Gigatoken’s scalar reference, an isolated 2.5x to 2.6x improvement.The r50k module notes report this isolated throughput. That figure covers boundary detection. Turning each span into token IDs remains downstream work.

2. Cache the final IDs for each pretoken

After pretokenisation, an encoder normally runs the BPE merge loop for each span. Gigatoken memoises the final token-ID sequence for the exact bytes of each ordinary pretoken. For an unseeded pretoken, the first occurrence computes the tokeniser’s normal answer; later occurrences copy the saved IDs. Each cache entry stores one pretoken’s final IDs; merge histories and whole-request outputs stay outside the cache.

Pretokens up to 15 bytes use a custom short-key table, while longer ones use a separate map. The short table is seeded with exact results for vocabulary byte strings from 1 to 15 bytes. A reused tokeniser instance keeps its results across calls and continues warming.

For a fixed tokeniser, the same pretoken bytes always produce the same IDs, so the cache can replay them without changing the result. The tokeniser’s own rules generate seed values because a vocabulary entry’s ID can differ from the required answer. The 128-bit key contains the complete short byte string and its length, and the table compares that full key after hashing. A hash collision triggers another probe. Full-key comparison prevents it from returning another pretoken’s tokens. Differential tests compare the cached path with uncached encoding across the supported tokeniser families.Implementation and correctness checks: tokeniser-aware seeding, key packing and hashing, and full-key cache probes.

On the author’s 1 GB GPT-2/OpenWebText run, the table accumulated about 1.3 million unique short pretokens and served 99.4% of lookups as hits. About 90% of pretoken occurrences emitted one token and 98% emitted no more than two.The cache source records the OpenWebText distribution and layout rationale. In that workload, most spans skip the pair-rank lookups, merge decisions and scratch-state updates described in the next section. A hit finds the cached entry and copies its token IDs.

Fetch the key and answer together

Once caching removes the merge algorithm from the common path, the remaining cost is a largely random table lookup. Processors fetch memory in fixed blocks called cache lines. The x86 machines discussed here use 64-byte lines; the Apple M3 Pro in my benchmark uses 128-byte lines. L1 is the smallest and fastest cache near each core; L2 and the shared last-level cache hold more data at higher latency. A load that misses them may leave the core waiting for main memory.

A short pretoken and its length fit in one 128-bit key. A hash chooses an aligned home pair in the open-addressed table. Where available, Gigatoken calculates the hash with CPU checksum instructions; other targets use a portable arithmetic fallback. Each entry is 32 bytes, so both candidates form one 64-byte probe bucket that fits within a hardware cache line on both architectures. Gigatoken loads both keys and inline values together, compares the complete keys, and selects the match in registers. The common probe requests the bucket’s cache line and avoids a metadata fetch followed by a dependent random load of the value.

Collisions probe later buckets. Up to four token IDs live inside an entry; larger answers spill into a separate append-only token buffer. Offsets and lengths keep cache entries valid across buffer reallocations.

Gigatoken processes up to 256 pretokens as a group. While it discovers their spans, it asks the CPU to prefetch each future target line into L2. During the probe pass it requests promotion into L1 sixteen entries before use. The CPU may ignore a prefetch hint. When it honours one, independent work overlaps the memory fetch and reduces the chance that the probe waits for that line.

The common inline emit path also spends a few extra stores to remove control flow. It reserves room for four token IDs and writes all four lanes from the cache entry. The cursor advances only by the true count, so unused lanes are overwritten by the next result or truncated at the end. That avoids a count-dependent ladder of one-token, two-token, three-token and four-token branches.

The published A/B measures the combined probe-and-emit design: memoisation, staged prefetch, inline four-token values and flat output. On the campaign’s cold 10 GB GPT-2/OpenWebText benchmark, that combination was 27.6% faster in the single-threaded path that materialised the token IDs and 6.2% faster on the multithreaded path.The profiling campaign records both A/Bs under their separate controls.

Reduce address-translation work on Linux

The cache works on ordinary memory pages. On Linux, huge pages can reduce the address-translation overhead as a randomly probed table grows. Before a core can load a cache entry, it must translate the program’s virtual address into a physical address. The processor keeps recent translations in a translation lookaside buffer, or TLB. If the translation is absent, a page-table walk must find it first. On Zen, a software prefetch that misses the data TLB may be dropped, weakening the prefetch ladder described above.

A 64 MiB table occupies 16,384 ordinary 4 KiB pages. Full backing by 2 MiB huge pages reduces that to 32 pages. Gigatoken therefore aligns a large short-cache allocation to 2 MiB on Linux and calls MADV_HUGEPAGE before the memory is first touched. If Linux honours the hint, fewer translations have to cover the same table.

In a separate Zen 5 whole-encode comparison, huge pages reduced warm page walks from about 28.6 million to about 2,300 per pass and improved warm throughput by 7.3%.The Zen 5 profile records the page-walk A/B; Linux documents transparent huge pages. Because the A/B covered the input and output, the result captures address translation across the whole path. The allocation hint is Linux-specific and does nothing on macOS.

3. Make pretoken-cache misses cheaper

A pretoken-cache hit skips BPE. On a miss, the encoder must run the merge loop for that pretoken. Each merge changes up to two neighbouring candidates, so the next choice depends on the previous one. Gigatoken keeps that ordering serial while shortening pair-rank lookups and reusing temporary storage.

Some BPE vocabularies assign merged token IDs in merge-priority order, allowing the ID to rank a candidate. Others store merge rank separately from token ID.Merge priority and token ID can differ. Gigatoken detects that case and includes a reversed-ID test. Gigatoken preserves whichever ordering the tokeniser defines. For an ID-as-rank vocabulary that fits its packed representation, pairs whose IDs are both below 2,048 use a dense 16 MiB grid; other pairs use a packed sparse table. Both replace a general map with a shorter chain of dependent memory loads.See the dense and sparse pair-rank layouts.

Short and medium spans use fixed local rank and neighbour arrays with a linear scan. Long spans use reusable index arrays as a linked list plus a minimum heap, a priority queue that returns the lowest rank. On the ID-as-rank path, Gigatoken retains those arrays and the heap capacity between calls, avoiding fresh allocations for each cache miss. Both paths preserve merge priorities and choose the leftmost candidate when ranks tie.

On a 1 GB GPT-2 run on Zen 5, widening the dense grid to 16 MiB improved whole-encoder single-threaded throughput by 2.8% with a cold pretoken cache.The Zen 5 notes record the 16 MiB dense-grid A/B. Once warm, the cache’s 99.4% hit rate starves this path of work, and the gain disappears.The same dense-grid A/B found no warm-cache gain.

4. Parallelise across proven boundaries

Hugging Face Tokenizers and tiktoken parallelise across caller-supplied inputs, so a million-token document remains one item. Gigatoken finds proven boundaries inside that document and assigns its chunks to several workers.Hugging Face parallelises over caller-supplied inputs; Gigatoken's benchmark notes describe its whole-file input.

Gigatoken cuts at proven pretoken boundaries, which BPE cannot cross. Added and special tokens stay intact. Inputs with no safe cut stay serial. Tests compare the parallel output with the serial token IDs in their original order.See Gigatoken's safe split-point logic and equivalence tests.

Keep coordination outside the token loop

Workers share immutable vocabulary and pair-rank tables. Each worker owns its pretoken cache and scratch buffers, keeping locks and cross-core traffic from shared writes out of the per-pretoken loop.

Workers claim chunks through an atomic counter. Because the chunks are arranged from largest to smallest, the largest are claimed first while smaller tail chunks keep cores busy near the end. Strict ordering prevents a large chunk from starting late and becoming the final straggler.Source: tail-aware chunk sizing and strict work handout.

Copy results while the tail is still encoding

Gigatoken reserves flat output space and uses a commit cursor to copy the ready prefix while later chunks are still encoding. This overlaps result copying and first-write page allocation with useful work. If the reservation is too small, it gathers the completed chunk buffers after encoding.Source: opportunistic output commits and fallback gathering.

In separate A/B comparisons, the 16-thread path was 6.2% faster with strict handout plus parallel gathering and 4.4% faster with opportunistic prefix copying, each against its own control.The campaign records 6.2% for work handout and gathering and 4.4% for prefix copying.

The closest published total comes from the campaign’s final same-session comparison on a cold 10 GB GPT-2/OpenWebText encode. Its documented single-thread path reached 1,039 MB/s, while the 16-thread path reached 8,792 MB/s. That is about 8.5x the wall throughput, equivalent to cutting the 10 GB encode from roughly 9.6 to 1.14 seconds. Each worker runs the scanner, cache and miss paths described above, so parallelism scales the faster core.The linked 8.5x campaign comparison uses two whole paths whose identity checks report slightly different token counts. A separate token-identical serial ragged path has no published timing, so the report cannot isolate parallel scaling.

What parallelism costs

Exclusive worker state removes shared-cache locking from the per-pretoken hot path. The trade-off is a cache per worker and duplicated warm-up work. In the author’s 16-worker profile, the state slots accumulated about 16 million distinct entries between them, compared with 5.5 million for a single cache. Aggregate multithreaded CPU time was 14.7 seconds against roughly 11 seconds for Gigatoken’s single-thread run, even though wall time fell sharply. The request finished sooner by spending more aggregate CPU work and memory.

Initial short-cache sizing is clamped between roughly 2 and 128 MiB per state slot, depending on the predicted share of the batch. The tables can continue to grow, however. The short cache has no eviction, and the long-key maps and token arenas are append-only. The pool keeps that memory across requests. One user processing several terabytes reports in an open issue that Gigatoken eventually consumed the RAM and swap of a 1 TB server.The multithreaded profile measures duplicated cache work; issue #36 reports unbounded growth in a long-running job.

The wall-time gain therefore comes with a production requirement: long-running workloads with continually changing input need a way to bound or evict retained cache state.

What the Rust core achieved

Gigatoken’s 1,000x headline compares its native whole-buffer API with Hugging Face Tokenizers through its Python-facing batch API. Hugging Face’s encoder also runs multithreaded Rust. The headline includes the advantages of handing Gigatoken one 11.9 GB byte buffer, letting it find its own split points and avoiding compatibility work at the Python boundary.The README notes that Hugging Face already runs multithreaded Rust and compatibility mode falls short of 1,000x. The benchmark also gives the systems different input shapes.

My service already used a multithreaded Rust tokeniser core. My benchmark therefore compared two Rust cores. As I reported in my first Gigatoken post, the timed million-token, 1,024-segment count path fell from about 159 milliseconds to 4.24 milliseconds, a 37.6x speed-up.

Together, the four mechanisms show how Gigatoken changes the way tokenisation runs on the hardware: classify 64 bytes at once, lay common cache probes out in 64-byte buckets, shorten the BPE miss path and parallelise at safe boundaries. GPU kernels receive this scrutiny as a matter of course. CPU preprocessing should too.