TLDR; Snappy OSS tokenizer; ~40x faster than hf, ~2x faster than gigatoken on BPE, and ~60x faster than hf on Unigram.

Note: Most of the content is in the “Optimizations” and “Internals” sections, but for people who HATE alpha, the API usage, AI usage, and benchmarking sections are written to be self-contained.

Snaptokens is a BPE and Unigram tokenizer written in Rust, bit-identical to hugging-face tokenizersIt is it is 2.19× faster than Gigatoken, 13.06× faster than fastokens, and 46.41× faster than Hugging Face To the best of my knowledge, that makes it the fastest open-source BPE and Unigram tokenizer available today.

This blog post will dive into (some) internals, optimizations, and the development process. Assumes good fundamentals about language modeling and perf optimization.

How do tokenizers work

The goal of a tokenizer is to take words and turn them into token IDs. These token IDs are used as indexes in an embedding table to get a pre-determined vector. This vector is then used as the initial hidden state of a transformer¹.

The core requirement of a tokenizer is to create tokens which represent a coherent portion of a word, whilst being small enough to be an elementary unit. ²

Two obvious answers both fail:

• One token per word. Any word outside the table becomes an unknown token. The model cannot read it, and cannot write it.
• One token per character. Coverage is complete, but sequences become very long. Attention cost grows with the square of the sequence length, so this is expensive.

Thus, we come up with clever algorithms (BPE, Unigram, WordPiece, etc.) in order to get this task done.

"snaptokens outperforms everything"

 sn      apt     ok     ens     ␣outper    forms    ␣everything
 16184   2373    482    641     33597      23914    2279

Tokenization is split up into encoding (words→ids) and decoding(ids→words).

The decoder is simply mapping IDs back to standardized text. Tokenizer libraries do not handle stripping post-processor templates, so all decode does it apply the inverse of the algorithm chosen

Common pre-tokenizers include:

• WhitespaceSplit — splits at whitespace and discards it: “hello world” → [“hello”, “world”].
• Metaspace — replaces spaces with a visible marker (usually ▁) and splits on it: “hello world” → [“▁hello”, “▁world”]. The SentencePiece convention, paired with Unigram and SentencePiece-style BPE models.
• Split — a raw regex the tokenizer configuration supplies, with a behavior flag saying how regex matches are handled.

Common post-processors include:

• TemplateProcessing — the file spells out a template like <s> $A </s> (and a second one like <s> $A </s>, or <s>$B </s> for sentence pairs), and encoding pastes the IDs into it. This is where the 1 and 2 in the table’s example come from.
• BertProcessing / RobertaProcessing — hard-coded ancestors of the template: [CLS] $A [SEP] for BERT, <s> $A </s> for RoBERTa. Newer files express the same thing through TemplateProcessing.

We add special tokens such as:

• <unk>: The default token for text the vocabulary cannot represent.
• <pad>: A filler token to make ragged batches the same size.
• <|im_start|>, <|user|>, <|assistant|>: The chat-template structure used for instruction-tuned models.

Tokenizer Algorithms explained

Byte Pair Encoding (BPE)

BPE³ was not designed originally designed for language. Philip Gage published it in 1994 in The C Users Journal as a compression method. His version replaced the commonest pair of bytes with a byte value that the data did not use, wrote the substitution table beside the compressed data, and repeated. He reported compression close to LZW with a faster and smaller expansion routine, which suited machines with little memory.

BPE training merges the most frequent character pairs until we hit a pre-determined vocab size.

The following is pseudocode to train a BPE tokenizer.

count the words in the corpus            # word → frequency
split each word into symbols             # characters, or bytes
repeat until the vocabulary is full:     # **outer loop**
    count every adjacent symbol pair, weighted by word frequency
    take the pair with the highest count
    append that pair to the merge list
    replace that pair with one symbol everywhere

Training produces one artifact—an ordered list of merges.

Here is a snippet of the gpt-2 merge table:

During encode, we are given a merge table, and a vocabulary (token → id)

There are a few key details that make BPE appealing:

• Counts are weighted by word frequency. A word that appears 900 times contributes 900 to each of its pairs.
• When constructing character pairs, we never cross a word boundary. Intra-word merging is not allowed, keeping separation between tokens cleaner.
• As a result, BPE is natively parallel. The outer loop is not, as the next merge depends on the current one.
• It is entirely deterministic and very simple.

BPE’s characteristics make it a very prominent tokenizer algorithm, with virtually all modern models trained for BPE.

Unigram

Unigram is a less mainstream, albeit a very interesting tokenizer algorithm.

Kudo (2018) introduced it alongside subword regularization. The core difference compared to BPE is that BPE builds a vocabulary by merging upward and segments greedily, and Unigram starts with too large a vocabulary, prunes downward, and segments by finding the most probable path.

Training Unigram

The training process is the following:

1. Find substrings

We start with an exhaustive vocabulary, containing every possible character, and a large amount of substrings. To compute the substrings, we do the following:

• Find all the suffixes of a word, and sort them alphabetically. For example with banana, we get ["a", "ana", "anana", "banana", "na", "nana"]
• For each suffix, we will compute the LCP (Longest Common Prefix). This value represents how many leading characters a suffix shares with a suffix an index before it. For example, anana and ana share all of ana, so anana gets the value 3, for the 3 chars. Similarly, nana gets LCP of 2, since it shares na with na
• The amount of letters at the start of each suffix that two adjacent suffixes have in common, represents their depth. All suffixes that agree to a certain depth, form a block. For example:
  • ana and anana share 3 letters—ana. Thus, we can define ana and anana as a block of depth 3.
  • a, ana, and anana have a depth=1. So we can declare a block over these three suffixes.⁴

We then walk the suffixes("a", "ana", "anana", "banana", "na", "nana"), finding blocks. Once the suffix we are looking at dosen’t have the same first characters as the ones part of the current block, we close the block.

After each block is closed, we store the shared prefix for the block along with the size of the block (amount of suffixes involved in the block)

Here is how we walk the graph:

We are now left with something like this:

2. Score substrings

Then, we score each substring. $\text{Score} = \text{Count} \times \text{Length}$ ⁵

Longer substrings are ranked higher since they compress information better. We keep the top N by score. Then, regardless of score, we add every required character, all 256 byte pieces, if byte fallback is on, and all special tokens we allocated by hand.

3. Initialize probabilities

We now give each substring a starting log-probability:

where $c(x)$ is substring frequency.

We count how many times each piece occurs as a substring, and turns those counts into probabilities. This is intuitively quite crude. Probability should reflect how often a piece actually gets used, but raw counts assume every appearance is used, and appearances overlap and compete, so only one can win. The probs in this case also don’t form a coherent distribution.

Thankfully, these probs are meant to be replaced.

4. Our goal is to turn these naive probs into something more logical

There is a circular dependency:

• To know a piece’s probability, you need to know how often it appears in segments of words .
• To choose segmentations, you need substring probabilities.

To solve this, we use EM, in wwhich we alternate between expectation and maximization steps in order to converge onto accurate probabilities

4. Expectation–Maximization

Expectation

For each word, enumerate its segmentations⁶. Score each one as the product of its substrings’ probabilities, and normalize those scores so they sum to 1. We are guaranteed that segmentations are created of substrings, because we use the same corpus to create both, segmentations, and substrings.

The output is an expected count per piece: how often the piece is used, averaged over all segmentations, weighted by how likely each is.

For bandana split as band|ana, the normalized score is:

The normalizer is the sum of the scores of every segmentation of that word.

Here is a walk-through example of Expectation.

banana ×3

banana              0.743  →  banana +2.23
ban|ana             0.134  →  ban +0.40,  ana +0.40
ban|an|a            0.034  →  ban +0.10,  an +0.10,  a +0.10
ban|a|na            0.027  →  ban +0.08,  a +0.08,   na +0.08
b|an|ana            0.018  →  b +0.05,    an +0.05,  ana +0.05
... 12 more splits share the remaining 0.044


bandana ×2

band|ana            0.404  →  band +0.81,  ana +0.81
ban|dana            0.253  →  ban +0.51,   dana +0.51
band|an|a           0.102  →  band +0.20,  an +0.20,  a +0.20
band|a|na           0.082  →  band +0.16,  a +0.16,   na +0.16
b|an|dana           0.034  →  b +0.07,     an +0.07,  dana +0.07
... 22 more splits share the remaining 0.125

This produces:

Expected count is a substring’s weighted usage across the corpus, averaged over all segmentations. We calculate expected count for the entire corpus, for all substrings, ending up with one value per substring.

Maximization

Maximization simply turns expected count values back into probabilities

Thus, the table above becomes:

5. Pruning

Thus far, we have been quite generous with allowing a very large set of tokens. In the effort of fixing this, we prune tokens that are redundant. and whose work another piece can absorb costs almost nothing to delete.

1. First, we run Viterbi once per word to find the optimal segmentation. Using that information, we count how often each substring is used. Call that freq[x].

Viterbi is an algorithm that finds the single best path through a set of choices, without checking every path.

To fill best[k], look at every piece that ends at position k. Each one starts somewhere earlier, at j. The score is best[j] + score(substring).

For example, Viterbi to compute optimal segment for bandana:

2. We can then delete every piece with freq[x] = 0. We have a new, smaller vocab set.
3. With the vocab we are left with, we find the best way to segment surviving substrings using the rest of the vocabulary. We then measure the cost of every replacement substring. ⁷

How do we compute loss though?

Three inputs, all already available:

• freq(x): how often Viterbi used the piece, from step 1.
• A(x): the replacement segmentation, from step 2.
• loss(x): the price of deleting piece x

The bracket measures how much score is lost after after replacing with replacement substrings. Multiply by the number of places this happens, and we get loss.

Looping during training

After doing initialization via steps 1-3, we repeat steps 4 and 5, tuning and pruning recursively, until we get to our desired vocab size.

For example:

  → EM ×2 → cut 25% → 750,000
  → EM ×2 → cut 25% → 562,500
  → EM ×2 → cut 25% → 421,875
  → ...
  → 32,000  ← stop

Unigram encoding

During encode we are given a vocabulary where substring maps to an ID and a log probability. The log probability scores how good that substring is, and using Viterbi we pick the segmentation who scores highest.

Hugging Face’s tokenizer.json is the standardized implementation for storing information to use a tokenizer. It stores relevant data and metadata in one file.

The following example is for BPE:

{
    "normalizer": {
      "type": "Lowercase"
    },

    "pre_tokenizer": {
      "type": "WhitespaceSplit"        // Discard whitespace and encode each piece separately.
    },

    "model": {
      "type": "BPE",
      "vocab": {                       // Token spelling → token ID; IDs don't set merge priority.
        "[UNK]": 0,
        "h": 1,
        "i": 2,
        "hi": 3,
        "t": 4,
        "e": 5,
        "r": 6,
        "th": 7,
        "there": 8,
        ...
      },
      "merges": [                      // Earlier entries have higher priority.
        ["h", "i"],                    // Each pair merges into its concatenated spelling.
        ["t", "h"],
        ["th", "e"],
        ["r", "e"],
        ...
      ],
      "unk_token": "[UNK]"             // Used when the vocabulary cannot represent input.
    },

    "added_tokens": [
      {
        "id": 0,
        "content": "[UNK]",            // Recognize this spelling without splitting it through BPE.
        "single_word": false,          // Matching doesn't require word boundaries.
        "lstrip": false,               // Don't absorb whitespace before the match.
        "rstrip": false,               // Don't absorb whitespace after the match.
        "normalized": false,           // Match before normalization.
        "special": true                // Can be omitted when decoding with skip_special_tokens.
      }, 
      ...
    ],

    "post_processor": null,            // No additional processing, such as inserting special tokens.
    "decoder": null                    // No custom transformation to reverse ByteLevel or Metaspace.
  }

The optimization section will contain higher-level algorithmic stuff and the internal section will contain lower-level CPU perf stuff. The latter will show more code.

Optimizations

Snaptokens implements BPE and Unigram tokenization in Rust, with hugging face exact Python bindings. We will break down the parts that compose of snaptokens here.

Scanners

Scanners (src/pre_tokenizers/scanner) split text into the chunks that BPE processes separately. For example, a scanner might split “hello world!” into “hello”, ” world”, and ”!”. Most tokenization libraries accept regex to define how we split the input, and pass it to an external dependency to process.

However, there is a neat pattern we can take advantage of—most models use the same regex. Because of this, specialized scanners implement common regex patterns directly. Specialized scanners only need to handle one known pattern, so they can do less work than a general regex engine.

Modern regex engines construct a state machine (or in modern implementations, multiple) by compiling the regex, then walking through the input and providing results after working. ⁸ They are required to support arbitrary regex, meaning the implementations are generalized, which in programming, often corresponds to slow.

On the other hand, we can exploit relationships between the specific splitting rules to avoid checks and redundancy, and perform other algorithmic optimizations, since our path is predetermined. We also can add CPU other optimizations (branch reduction, cache locality, etc).

We also use SIMD for specialized scanners. SIMD lets us apply the same check to several bytes with one instruction. Instead of checking 16 characters individually for spaces, we check all 16 together.

For “cat dog”, SIMD checks all seven bytes for letters together. Written in input order, the resulting mask is:

  Input:                c a t   d o g
  Is a letter:          1 1 1 0 1 1 1
  Previous is a letter: 0 1 1 1 0 1 1
  Word starts here:     1 0 0 0 1 0 0

Shifting the “Is a letter” mask right 1 place, gives the “previous is a letter” row (mask b). Combining the information from these two bitmasks, we get “Word starts here”, which marks c and d accurately.

Fusing common paths

There are two major things we can exploit (at an architectural level) to get huge speedups:

• A majority of BPE tokenizers use ByteLevel as their pre-tokenizer ⁹
• A majority of Unigram tokenizers use the WhitespaceSplit and Metaspace pre-tokenizers, back-to-back.

For reference:

• WhitespaceSplit splits at whitespace. For example, “hello world” becomes [“hello”, “world”].
• Metaspace replaces spaces with a visible marker, usually ▁ For example, “hello world” becomes [“▁hello”, “▁world”]
• ByteLevel: With all 256 byte values in its starting vocabulary, a byte-level BPE tokenizer can represent any UTF-8 text, including characters absent from its training corpus. This also restricts BPE’s starting alphabet to 256 symbols, while learned merges can expand the final vocabulary far beyond that. For example, it represents the space byte as Ġ, so “hello world” can become [“hello”, “Ġworld”].

We exploit these common combinations by joining stages that would otherwise build intermediate results for the next stage to consume.

For ByteLevel + BPE, the usual pipeline splits the text into pieces, converts their bytes into ByteLevel’s character representation, then runs BPE on each piece to produce token IDs.

Our fused path passes the scanner’s UTF-8 bytes directly to BPE, using a precomputed table to map them to initial token IDs before applying the merge rules. For example, a space maps directly to the initial ID associated with Ġ, without constructing a string containing Ġ. This saves intermediate storage, copying, and conversion work.

Normally:

original byte → ByteLevel character → BPE token ID
space         → Ġ                  → ID for Ġ

Our fused path combines those two mappings:

original byte → initial BPE token ID
space         → ID for Ġ

For Unigram, the usual pipeline splits the text at whitespace, then applies Metaspace to each word. Our fused path combines whitespace splitting with preparing the Metaspace pieces. For large inputs, we also divide the text at safe whitespace boundaries so threads can process independent portions.

  Normally:

  "hello world"
      → ["hello", "world"]       WhitespaceSplit
      → ["▁hello", "▁world"]     Metaspace
      → token IDs               Unigram

  Our fused parallel path:

  find "hello" → prepare "▁hello" → Unigram → append IDs
  find "world" → prepare "▁world" → Unigram → append IDs

Distributing and parallelizing independent work

Revisiting the earlier section, we noted that doing computation for BPE and unigram is natively parallel, such that we can tokenize every word at the same time.

We divide adjacent slices of data into groups and distribute those groups across threads. Each thread processes its group sequentially. When our number of groups is more than # threads, we keep groups in a pool, and the a current available thread will pick one up. The ordinary paths complete pre-tokenization before distributing pieces across threads. BPE targets one group per thread, while Unigram targets two. ¹⁰

The fused BPE path targets two groups per thread, giving the scheduler additional work to distribute when some groups finish sooner. Unigram has 6 groups per thread.

Normalization rules can match multiple characters, such as replacing “a b” with “x”. If we divide the text between “a ” and “b”, neither task sees the full match. We therefore normalize sections independently only when our boundary checks preserve the result; otherwise, we normalize before dividing the input.

We choose the group count and size to balance keeping threads busy against the overhead of creating and processing groups.

Empirically, these group sizes have performed best:

$P$ = thread count, $N$ = piece count, $L$ = input length in bytes.

For small inputs, we skip internal multithreading and process the input on one thread since scheduling overhead can outweigh the time saved by parallel execution. For large enough BPE batches, we parallelize across inputs rather than within them, since separate inputs already provide enough work to occupy the thread.

The .st filetype

A .st file is a saved representation of a tokenizer.

The optimizable surface we can discuss is that the tokenizer.json is not the representation our encoders use directly. This is best proven via example:

Consider a tiny BPE model:

  {
    "vocab": {
      "h": 0,
      "i": 1,
      "hi": 2
    },
    "merges": [
      ["h", "i"]
    ]
  }

During JSON loading, Snaptokens must parse the strings, convert merge lists to IDs, and prepare other structures. The merge above becomes something equivalent to:

  Input token pair:  (0, 1)
  Merge priority:   0
  Result token ID:  2

If we store the precompute used data structures as opposed to computing them after loading the JSON, we can save time when loading tokenizer data.

What the file contains

The file has an 52-byte header, followed by a binary payload:

  tokenizer.st
  ├── Header
  │   ├── File identifier   # Identifies filetypes, even if someone changes the file extension
  │   ├── Format version    # Tell loader whether we are loading BPE (v3) or Unigram (v4)
  │   ├── Payload length    
  │   └── Payload checksum  
  └── Payload
      ├── config_json  # Config data like normalization, padding, truncation, etc.
      └── BPE tables or Unigram model inputs  

For BPE, the payload stores vocabulary spellings together in one byte buffer. Suppose token IDs 0, 1, and 2 represent “snap”, “token”, and “s”:

Byte index:    0  1  2  3  4  5  6  7  8  9
Stored byte:   s  n  a  p  t  o  k  e  n  s

Offsets:      [0, 4, 9, 10]

For token ID n, offsets[n] marks its start and offsets[n + 1] marks its end, excluding the ending position:

ID 0: bytes [0, 4)  → "snap"
ID 1: bytes [4, 9)  → "token"
ID 2: bytes [9, 10) → "s"

We then store the byte offsets and concatenated tokens in two vectors, in a struct called PackedVocabulary. This helps us convert from IDs → words. This is how the struct looks:

  struct PackedVocabulary {
      bytes: Vec<u8>,
      offsets: Vec<u32>,
  }

However, we still need to convert token spellings into IDs. PackedVocabulary stores spellings in token-ID order, so finding an ID from a spelling would require searching through the vocabulary.

To resolve this, we use VocabLookup to provide this reverse lookup efficiently.

 struct VocabLookup {
      mask: usize,
      hashes: Vec<u64>,
      ids: Vec<u32>,
  }

An eight-slot lookup could look like this:

Slot:     0   1   2   3   4   5   6   7
Hash:     0   9  17   0   0   0  22   0
Token ID: —   0   2   —   —   —   1   —

  mask = 7  # selects the bits of a hash that determine the array position

To find “s”:

1. Compute its hash: suppose it is 17.
2. Calculate the starting slot: 17 & 7 = 1. Since the capacity is a power of two, this works like 17 % 8.
3. Slot 1 contains hash 9, so check the next slot.
4. Slot 2 contains hash 17, pointing to token ID 2.
5. Retrieve ID 2’s spelling from PackedVocabulary and compare its bytes with “s”. They match, so return 2.

This turns out to be more performant than a naive hash map because we store token hashes as opposed to token strings.

We also save each entry’s slot position in .st, so loading can restore the table directly instead of searching for a position for each entry through repeated insertions. like so:

 In memory:
      Slot:     0      1      2      3
      Entry:  empty   A    empty    B

  Saved in .st:
      Capacity: 4
      Entries:  (slot 1, A), (slot 3, B)

• RankedMergeMap maps pairs of token IDs to their merge rank and resulting token ID.

  struct RankedMergeMap {
      mask: usize,
      keys: Vec<u64>,   // Two 32-bit token IDs packed into each key.
      values: Vec<u64>, // Merge rank and resulting token ID, each 32 bits.
  }

The impact of having this information stored in .st is fairly minor. This work happens when a tokenizer is loaded, and encoding commands reuse the structures already in memory.

Preparing lookup tables at compile time

For any circumstance (.st or .json), when we load data, we generate and store the following:

• Initial byte-pair table: Looks up a merge directly from two input bytes. For example, “s” followed by “n” might return priority 7 and the token ID for “sn”. It contains all 256 × 256 = 65,536 byte combinations, with pairs that cannot merge marked as such. We always build this table , using the saved byte-to-token mapping and RankedMergeMap.

Its purpose is to quickly find which neighboring bytes can merge when BPE starts processing a piece.

For “snap”, the starting pairs are:

  "s" + "n"
  "n" + "a"
  "a" + "p"

The data structure looks like this:

byte_pair_initial: Vec<(u32, u32)>,

The table gives each pair’s merge priority and resulting token ID directly. BPE compares the priorities to decide which merge happens first.

• Dense merge table: Looks up a merge directly from two inital token IDs, including tokens produced by earlier merges [^]: “sn” and “ap” might merge into “snap”. Each pair is stored at left_id * width + right_id, where width is the number of token IDs covered on each side. there are two different types of dense merge tables.

We build dense_ranked_merge for all initial token IDs—the IDs of individual tokens before BPE applies any merges. dense_ranked_merge is best explained through example:

Suppose our tokenizer has two merge rules:

The first four rows and columns of dense_ranked_merge would look like this:

Each cell contains the resulting token ID.

Using dense_ranked_merge makes querying much more efficient, getting O(1) lookup time.

If that variant cannot be built, dense_merge will be built if all initial byte-token IDs are below 512. dense_merge handles tokenizers whose resulting token IDs don’t encode merge priority. When using dense_merge we have to store rank separately, compared to dense_ranked_merge, where every resulting token ID is the rank shifted by the same fixed amount. dense_ranked_merge is also O(1) lookup.

If neither qualifies, we build neither. Pairs outside a built table’s range use MergeAdjacency.

MergeAdjacency is BPE’s general lookup structure for finding a merge’s rank and resulting token ID. It stores rules grouped by their left token, with each group sorted by right token ID.

For example:

  Left token 10 ("sn"):
      Right token 20 ("ap") → rank 7,  result 30 ("snap")
      Right token 40 ("ow") → rank 12, result 50 ("snow")

To look up (10, 40), it finds token 10’s group, binary-searches for 40, and returns (12, 50).

Those groups are packed into three arrays:

  struct MergeAdjacency {
      offsets: Vec<u32>, // Start and end of each left token's group.
      keys: Vec<u64>,    // Right token ID and rank, packed together.
      new_ids: Vec<u32>, // Corresponding resulting token IDs.
  }

• Character-to-token tables: These map individual characters directly to initial vocabulary IDs. If token ID 12 spells “s”, the entry for “s” contains 12, avoiding a string-hash lookup. Loading always builds a table for Unicode code points below 65,536 a table for all ASCII codepoints. Characters without a matching vocabulary token remain marked “no token”, and don’t use Character-to-token tables.

• Token-length table: Before running BPE merges, the encoder looks for a valid vocabulary token matching the beginning of the input piece. This table checks whether that token covers the whole piece by comparing their byte lengths. For example, the vocabulary token “snap” covers all of “snap”, but only the beginning of “snaps”. If it covers the whole piece, we return its ID immediately. During loading, we calculate each token spelling’s byte length from neighboring vocabulary offsets and cache it in a one-byte-per-token table. Lengths below 255 bytes are stored directly. For longer spellings, we store 255 as a marker and calculate the exact length from the offsets when needed.

Unigram algorithmic optimizations

When loading a Unigram model, we store its token ↔ ID and scores in separate arrays, both indexed by token ID:

  pub struct Unigram {
      id_to_token: Vec<String>,
	  scores: Vec<f64>, 
      token_to_id: HashMap<String, u32>,
      automaton: Option<DoubleArrayAhoCorasick<u32>>,
      unk_id: Option<u32>,
      min_score: f64,
      byte_fallback_ids: Option<[Option<u32>; 256]>,
  }

When loading the tokenizer, we build a matcher from vocabulary strings and their token IDs.

During encoding, the matcher finds those strings in the input and reports their IDs. For example, if “snap” has ID 2, a match returns 2. The encoder then reads scores[2], without looking up “snap” in the hash map.

A matcher is a search structure that finds vocabulary strings inside the input (ex. find index of word “snap” inside a paragraph). For tokenizers, we want overlapping matches as well (ex. find “snap” and “snaptoken” inside of “snaptokens”)

The naive implementation of a matcher is to start a prefix-tree search.

An example of a prefix tree:

  root
   ├─ s → n → a → c → k   "snack"
   └─ n → a → p           "nap"

At each character position in the input, we start at the root and follow the input bytes until a branch is missing. Whenever we reach a complete vocabulary entry, we report it. An example:

The more efficient implementation actually used is Aho–Corasick ¹¹. It works in a similar prefix-tree fashion, but it allows for the ending of the bytes already read to begin another vocabulary string.

Every node stores a pointer for the longest proper suffix that exists in the trie. After we hit a dead end, we can jump to this value, and continue onwards, rather than jumping to the root. Sometimes the longest proper suffix is also part of the vocab (ex.range is a part of orange).

Searching “snap” now proceeds like this:

We do not reread n and a. We preserve that partial match while the input scan continues forward

The double-array representation is how daachorse stores the search structure in memory. We store children using BASE and CHECK.

• BASE[s] — an offset owned by node s. Offsets are numbers assigned to each node at build time, used to compute where its children live. Nodes with children on the same character are forced onto different numbers. This is because we compute BASE[s] ^ char, and each input has to be unique
• CHECK[slot], where slot = BASE[s] ^ byte — an array of node IDs, indexed by slot. The slot number is the child node ID, and the value stored there is the parent that claimed it. So node s computes a slot from its own offset and the current char, then reads which node is it’s parent. If the owner is s, the transition is real and the slot number becomes the new current node. If it is any other node, the arithmetic landed in a slot belonging to someone else, so s has no child on this byte and we assume we hit a dead-end.

Here is an example of Aho-Corasick with double-array:

Assume the following:

The lookup works like this:

sna + 'p'    slot = BASE[3] ^ 112 = 0 ^ 112 = 112
             CHECK[112] = 3 = sna      ✓   →  s = 112   (snap)

s   + 'n'    slot = BASE[1] ^ 110 = 1 ^ 110 = 111
             CHECK[111] = 1 = s        ✓   →  s = 111   (sn)

root + 'q'   slot = BASE[0] ^ 113 = 0 ^ 113 = 113
             CHECK[113] = 6 = na       ✗   →  no child, assume dead-end

Internals

This section will discuss abstractions used and lower-level CPU performance optimizations to snaptokens.

The Tokenizer struct is the tokenizer.json section from part one, literally:

pub struct Tokenizer {
    added_tokens: Option<AddedTokens>,
    normalizer: Option<Normalizer>,
    pre_tokenizer: Option<PreTokenizer>,
    model: Model,                        // BPE or Unigram
    post_processor: Option<PostProcessor>,
    decoder: Option<Decoder>,
    needs_vocab_splitting: bool,
}

Each field here maps one-to-one to sections of the JSON. Model is simply an enum between Unigram and BPE and the rest of the fields are data structs.

The natural implementation of pre-tokenize-then-encode is a Vec<String> of pieces between the two stages. Snaptokens’ fused paths avoid creating an intermediate buffer. The scanner and the encoder are connected by a sink:

pub(crate) trait FusedPieceSink {
    // We pass in a ref to the input, and indexes, return nothing, and 
    unsafe fn push_piece(&mut self, input: &str, start: usize, end: usize);

    // Batch form: consume a whole 64-bit boundary bitmask at once.
    unsafe fn push_mask(&mut self, input: &str, mask_base: usize, start: &mut usize, mask: u64);
}

push_piece hands the sink one finished piece, identified as the byte range start..end of input, and returns nothing because the sink absorbs it into its own state, such as a pending queue or an output buffer. push_mask provides the sink up to 64 pieces at once, where each set bit i in mask to mark a piece ending at byte mask_base + i.

For the window covering bytes 0–63 of “the cat sat”:

input:    t h e c a t s a t ...
mask:     0 0 0 1 0 0 0 1 0 ...   = the u64 0b10001000 = 136

start is a cursor tracking where the current piece began, advanced past each piece as it is consumed and carried across calls so a piece can span two masks. mask_base is the absolute offset from 0 -> the piece we are on i input

The FusedPieceSink trait is used often throughout the codebase, acting as a template regarding how abstractions should move data.

Storing pieces efficiently

The encoder is designed around the idea that almost every piece a scanner emits is short. A word plus its leading space is a handful of bytes. So the entire hot path is specialized for pieces of at most 15 bytes.

A major optimization is that a piece of 15 bytes or fewer never becomes a String. It becomes a u128: the bytes in the lower lanes and the length in the top byte. Since the piece is now guaranteed to be 16 bytes, we can store it directly inside the slot in the hash map. If we were using String, we would have to put a pointer in the slot in the hash map and then look up the pointer. Also String takes up an average of 24 bytes, while the u128 is guaranteed to be 16 bytes.

Here is an example:

piece " the" (4 bytes) as a u128:

position:   0    1    2    3    4  ...  14    15
contents:  ' '  't'  'h'  'e'   0  ...   0     4
		└── the text ──┘   └─ zeros ─┘   length

The following is code to pack data into a u128. On ARM NEON:

let raw    = vld1q_u8(input.as_ptr().add(start));           // 16 bytes, one load
let live   = vcltq_u8(LANES, vdupq_n_u8(len as u8));        // lanes 0..len
let packed = vsetq_lane_u8::<15>(len as u8, raw & live);    // zero the rest, tag the length

These are SIMD intrinsics to load the data, calculate bitmask to figure out what part of the u128 is real data, and erase the junk and write the length in the last byte

let raw = vld1q_u8(input.as_ptr().add(start));

Copy 16 bytes from the input, starting at the piece, into one CPU register. We only want the 4 real bytes, since the other 12 bytes are junk.
raw:  ' ' 't' 'h' 'e' 'c' 'a' 't' ...   ← 4 real + 12 junk

let live = vcltq_u8(LANES, vdupq_n_u8(len as u8));

LANES is the constant [0,1,2,...,15]. This compares each position number against the length (4): positions 0–3 are marked with 1's, and 4-15 are marked with 0's
live:  ✔ ✔ ✔ ✔ ✘ ✘ ✘ ... ✘

let packed = vsetq_lane_u8::<15>(len as u8, raw & live);

raw & live applies the bitmask in the effort of preserving values with 1's. Then vsetq_lane_u8::<15> overwrites byte 15 with the length, 4.
packed:  ' ' 't' 'h' 'e'  0  0 ... 0  4
         └── piece ──┘   └─ zeros ─┘  len

Using the u128 trick means we have to write more custom hashing and equality checks ourselves.

Caching efficiently

All except for CrossThreadCache are thread-local.

  piece (≤15 bytes, as u128 key)          piece (>15 bytes, as &str)
          │                                        │
          ▼                                        │
    1. DirectCache      one slot read              │
          │ miss                                   │
          ▼                                        ▼
    2. ProbedCache   search the ProbedCache   3. LongMapCache
          │ miss                                   │ miss
          └───────────────┬────────────────────────┘
                          ▼
    3. CrossThreadCache   one lock + hash map lookup
                          │ miss
                          ▼
                the actual BPE merge loop
                (result then inserted back into the tiers above)

1. DirectCache

direct_cache: Vec<DirectCacheSlot>   // 131,072 entries (4 MiB)

struct DirectCacheSlot {
    key: [u64; 2],   // the packed u128 — the piece's text, inline
    packed_head_value: u64,      // length + IDs 0 and 1
    tail_value: u64,  // IDs 2 and 3
}

DirectCache runs at O(1) worst-case time and O(1) space, because we can directly access any value. The index of a value is based off hash of the key. doing this creates two issues:

1. One problem is that the hash tends to be a really huge number, but the array only has 131,072 entries. Thus we compute h modulo 131,072. This effectively means keeping the bottom 17 bits and discarding the rest.
2. Hashing does mean that the pieces will often be clustered together, causing collisions in values. In hash maps this is typically solved by using/allocating space for next value. We resolve this by simply overwriting the value, changing worst-case time from O(N) -> O(1). This works especially well for caches because it provides a slight LRU effect.

Also, separating packed_head and tail is a really neat trick! This way, we can avoid unpacking the tail and can operate with it directly.

However, Value being packed does mean that value looks like this:

value:      [ len: 8 bits ][ id0: 24 bits ][ id1: 32 bits ]

So we have to enforce id0 to be < 2^24.

2. ProbedCache

probed_cache: Vec<ProbedCacheSlot>   // 262,144 entries (6 MiB)
pool: Vec<u32>                       // spill space for long answers

struct ProbedCacheSlot {
    key: [u64; 2],   // the same packed u128
    value: u64,      // tagged: ≤2 IDs inline, or a (len, offset) into the pool
}

The ProbedCache holds everything the direct tier evicted or refused. Specifically, results wider than 4 IDs, first IDs over 2²⁴, and every piece that lost a slot collision. Inserts are write-through, such that a computed result lands in both tiers at once.

ProbedCache is structurally very similar to a hash map. Similar to DirectCache, we compute the index of a value via $\text{hash}(\text{key}) \mathbin{\%} \text{entries}$ ¹², except ProbedCache has 2^18 entries, compared to the 2^17 of DirectCache.

However, unlike DirectCache, we don’t overwrite on insertion. Instead, we walk from the index we computed, skipping over keys that don’t match our key. An empty slot (all-zero key) marks the search as a miss. Since insertions always claim the first empty slot if your key existed, you’d have found it before reaching one.

That makes it expected O(1), and worst-case O(N).

Take an example:

Say  giraffe has home slot 9,301. To look it up:

slot 9301:  key = " cat"s key   → not mine, step forward
slot 9302:  key = " giraffe"s key → MINE → decode value, done

And to look up something absent, say  yeti with home slot 9,301:

slot 9301:  " cat"     → not mine, step
slot 9302:  " giraffe" → not mine, step
slot 9303:  all-zero key → EMPTY → stop. Definitive miss.

Most cached results contain one or two tokens, so our 24-byte slots store these results directly. The value’s lowest two bits act as a tag, indicating how data is stored:

Marking the tag as 0–2 give the number of token IDs stored directly in the value, which has room for two 31-bit IDs. Results that are more than 24 bytes (2+ token IDs) are appended to a pool—one shared Vec<u32> holding token IDs for multiple cache entries. If we mark the tag as 3, that indicates we are storing data in the pool. In our 24 byte payload, we store an offset identifying where the result starts in the pool, and a length telling us how many IDs to read.

We evict all at once instead of tracking recency like a normal LRU cache.When the table reaches 75% occupancy or the pool reaches 64 MB, we clear the keys and reset the pool such that incoming requests repopulate the cache. Because entries are never deleted individually, linear probing doesn’t need to mark when hash table entries are deleted. After every eviction there are more empty values, meaning we generally get to walk less.

When probing finds a result small enough for the direct cache, we also insert it there before returning it. This lets a frequently used piece regain its direct-cache slot after being displaced.

3. LongMapCache

long_map: FxHashMap<Box<str>, (u32, u16)>   // piece text → (offset, len) into the pool

The main issue with the u128 key is that it forces a maximum of 15 bytes of text. To address this we create the LongMap cache, which exists as a normal hash map. This is still expected to be O(1), but OFN lookups are relatively common. Importantly, in LongMap we do not store data directly. We store the (offset, len) as 6 bytes, pointing to the pool the ProbedCache spills into.

Note we use FxHashMap instead of the normal std::collections:HashMap. The difference is that FxHashMap uses the Fx hash, vs the randomly seeded SipHash 1-3 used for the generic HashMap. The FX hash function is cheaper but is less uniformly random. It empirically performs better here.

For reference, the median piece is 4–5 bytes and even the 99th percentile is under 40.

4. CrossThreadCache

struct CrossThreadCache {
    shards: Vec<Mutex<FxHashMap<String, Vec<u32>>>>,   // 64 of them
}

The previous three caches are thread-local. This is generally fine but if we have four threads that independently end up calculating merges for the same token, we waste a lot of effort.

The CrossThreadCache is consulted only after all three local tiers miss, and written to for every piece a thread computes.

Each shard is a hash map(FxHashMap) that only allows one actor at a time(Mutex<...>). The hash map uses the piece as a string as the key(String), and the value is the IDs (Vec<u32>).

Using multiple shards lets us bypass the latency of having to handle everything sequentially. To deal with deciding which shard to route to we compute hash(text) % 64. When we query, we route to the correct shard, and do a normal hash-map lookup. We then copy the IDs into the thread-local cache.

When an insert finds its shard holding the maximum, 16,384 entries, it clears that entire shard and then inserts its value. Brute force caching works especially well here because we get to avoid storing eviction information. Often recalculating a merge is less net overhead than storing eviction information.

Optimizing EncodeStream

The BPE encoder implements the FusedPieceSink trait with EncodeStream(src/models/bpe.rs). It is used so that the scanner can emit piece boundaries, and the encoder can immediately consume them via an intermediate buffer.

The DirectCache is 4 MiB and indexed by a hash, so a lookup lands on an effectively random slot. Random accesses into a table that size usually miss L2, and a miss costs dozens to hundreds of cycles. A loop that looks up one piece at a time stalls for that long on every word. The lookup itself is a handful of instructions; almost the entire cost is waiting for memory.

EncodeStream avoids the wait by prefetching. When the scanner completes processing a piece, we compute the slot address, tell the CPU to start fetching that cache line, and put the piece in a queue:

let slot = direct_base.add(index);
pending.write(FusedPiece { slot, key });    // 24 bytes, into a fixed stack array
prefetch(slot);                             // prfm pldl1keep / _mm_prefetch

The queue holds up to 256 pieces. When it fills, flush() walks it in order and performs the actual merging or software cache lookups. By then, each slot’s cache line was requested up to 256 pieces earlier and has long since arrived, so reads don’t stall anymore.

It turns out, by default safe Rust won’t hand out uninitialized memory, so the queue 7,680 byte array gets initialized by default, and initialized to zero. This busywork was eating 17% of the encoder’s time.

To fix this, we use the unsafe type, MaybeUninit. To compensate, however, Rust forces the code must use raw writes, specifically, ptr::write, to fill slots and the user of the data may only read the part it has already filled.

Here is the implementation:

let mut pending = MaybeUninit::<[MaybeUninit<FusedPiece>; FUSED_PIECE_CAPACITY]>::uninit();
let pending = unsafe { &mut *pending.as_mut_ptr() };

let mut stream = EncodeStream {
    model: self,
    cache: &mut cache,
    out,
    error: None,
    pending,          // borrowed, never copied into the struct
    pending_len: 0,
};

A core part of EncodeStream is figuring out which pieces are less that 16 bytes, since those ones can go through our faster layers of caches. The obvious way is to check the length of each piece as we go. Often however, all of the pieces in the unit we are processing are less than 16 bytes long. We try to answer the question up front by finding out if every piece in the mask¹³ is short.

From the perspective of the mask, a piece is the gap between two boundary bits. If two consecutive boundary bits are more than 15 positions apart, then we know that the piece we are looking at is not accessible to the fast path.

We create a smear by extending each boundary bit across the next 15 positions. First, shift the mask left by one, marking the position immediately after each boundary. Then repeatedly OR the result with a copy shifted left by 1, 2, 4, and 7 bits. Each step uses the already-expanded result, so each run grows from 1 set bit to 2, then 4, 8, and finally 15. For example, a boundary at bit 10 marks bits 11 through 25 in the final mask.

boundaries:   ...0001000000000010000...
after smear:  ...0001111111111111111...  

We store the result of the smear in nearby. We then check whether each boundary after the first is within 15 bytes of the preceding boundary:

mask & (mask - 1) & !nearby == 0

mask & (mask - 1) removes the first boundary bit. AND-ing with !nearby leaves only boundaries outside the smeared area. If the result is zero, every remaining boundary is close enough to the previous one, so those pieces are all short.

We check the first piece separately with first_gap <= 15, since its starting position isn’t in the mask.

Take an example. Suppose the boundaries are at 3, 12, and 30. Positions increase from left to right:

positions:           0–7      8–15     16–23    24–31

mask:                00010000 00001000 00000000 00000010
nearby:              00001111 11111111 11111111 11110001

mask & (mask - 1):   00000000 00001000 00000000 00000010
!nearby:             11110000 00000000 00000000 00001110
AND result:          00000000 00000000 00000000 00000010

Boundary 3 is cleared because the first piece is checked separately. Boundary 12 disappears because the smear covers it. Boundary 30 remains because the smear does not cover it. The result is nonzero (30 − 12 = 18 bytes), so that piece is too long.

BPE perf improvements

The textbook implementation of BPE rescans the whole piece after every merge to find the next-best pair, achieving O(n^2). Our implementation keeps the symbols in a doubly linked list and the candidate merges in a heap:

struct MergeScratch {                          
    symbols: Vec<MergeSymbol>,
    heap: BinaryHeap<Reverse<MergeEntry>>,
    heap_buf: Vec<Reverse<MergeEntry>>,
}                                               

When executing a BPE merge, we typically have to remove an element in the middle of a contiguous buffer of IDs, which in a normal dtype (a Vec), would require moving all the data after processing. For a doubly linked list, we just have to edit the links.

struct MergeSymbol { c: u32, prev: i32, next: i32 } // c is a token ID.

All the symbols sit in one contiguous block of memory, and prev/next are array indexes. We choose prev/next as indices rather than ptrs because they are half the size, and unlike pointers, they survive reallocation. All we do to merge symbol 2 into symbol 1 is set symbols[1].next = symbols[2].next

We use a heap to hold the candidates, since it is O(log n) . We seed it with every adjacent pair that can merge, and each round pops the minimum ranked value:

struct MergeEntry { key: u64, val: u64 } 

The key is a packed 8-byte value, containing the rank of the merge and the index of the token ID that tid1 and tid2 merge to in the array of MergeSymbol’s. The val is a packed value containing token ID 1, and 2, for a given merge.

key = [ rank    | position ]      Position of the merged value in the MergeSymbol's array.  
val = [ tid1    | tid2     ]      key and val are packed values

On every merge step for a piece we do the following:

1. Pop the lowest-rank merge candidate from the heap.
2. Check that the merge candidate is still possible. It recorded the two token IDs its pair had when it was pushed, and an earlier merge may have rewritten either one. Compare them against what the current token sequence holds now, and if they differ, drop the entry and pop again.
3. Apply the merge. The left symbol’s token becomes the merged ID, and the right symbol is unlinked from the list.
4. Push the new candidates this merge created to the heap. The merged symbol now borders a new left neighbor and a new right neighbor, so look up both pairs in the merge table and push an entry for each pair that has a potential merge.

Calculating on-stack for small pieces

Recall from the compile-time tables section that we create a bunch of tables that we load data from. We seed MergeScratch via these LUTs.

Since MergeScratch is wiped after processing the current piece, it seems wasteful to allocate in heap for small-enough pieces. Because of this, for pieces <= 15 bytes, we use a few small stack arrays instead:

let mut symbols = [0u32; 16];       // the token at each position
let mut next    = [0u8; 16];        // neighbor links, one byte each
let mut prev    = [0u8; 16];
let mut ranks   = [u32::MAX; 16];   // ranks[i] = rank of merging position i with its right neighbor

Using this path:

1. Initialize the arrays for the piece using the LUTs.
2. Scan ranks for the smallest value. If nothing is below u32::MAX, no merge applies anywhere, and we’re done.
3. Merge at the winning position: its token becomes the merged ID, and its right neighbor is unlinked.
4. After merging, the ranks stored for the left and right neighbor of the merged ID are stale, so we update it
5. Go back to step 2.

This stack-based faster path does scale O(n^2). This dosen’t matter too much, because n caps out at 15.

API Usage

Snaptokens loads an existing Hugging Face tokenizer.json and uses it to turn text into token IDs—the integers a model consumes.

In Python, install it with pip install snaptokens:

from snaptokens import Tokenizer

tokenizer = Tokenizer.from_file("tokenizer.json")
ids = tokenizer.encode("Tokenization should not be the bottleneck.").ids

The JSON file defines how text is normalized, split, and mapped to tokens, so you don’t need to configure these steps yourself. encode() returns an encoding object; .ids gives you its token IDs.

Some models expect markers around an input, such as tokens indicating the beginning or end of a sequence. To include those, pass add_special_tokens=True. This is on by default:

ids = tokenizer.encode("Hello, world!", add_special_tokens=True).ids

When processing multiple inputs, use encode_batch():

encodings = tokenizer.encode_batch([
  "The first document.",
  "Another document.",
  "One more.",
])

rows = [encoding.ids for encoding in encodings]

This lets Snaptokens distribute work across CPU threads when the batch is large enough to benefit. Results stay in the same order as the inputs, with a separate token sequence for each document.

You can also set a length limit when inputs need to fit within a model’s context window:

tokenizer.enable_truncation(max_length=512, direction="right")

Subsequent encodings keep at most 512 tokens, removing excess content from the end. The limit includes any special tokens you request.

Loading a tokenizer has its own cost requires Snaptokens to read its vocabulary and prepare the structures used during encoding. If you frequently restart a script or service, enable .st caching:

tokenizer = Tokenizer.from_file("tokenizer.json", st_cache=True)

The first load creates a tokenizer.st file beside the JSON. This stores the tokenizer’s data in a form that is more efficient to load, trading an additional file on disk for faster startup on later runs. It preserves the same tokenization behavior.

You can also load that file directly:

tokenizer = Tokenizer.from_file("tokenizer.st")

A valid .st file is reused without checking whether the original JSON changed. If you edit tokenizer.json, delete its .st file so the next cached load rebuilds it.

For applications already using Transformers, call patch_transformers() before loading a tokenizer:

import snaptokens

snaptokens.patch_transformers()

from transformers import AutoTokenizer

tokenizer = AutoTokenizer.from_pretrained("gpt2")
ids = tokenizer("Hello, world!")["input_ids"]

This lets you keep the familiar Transformers interface while using Snaptokens for encoding supported tokenizer pipelines.

The Rust API follows the same pattern:

use snaptokens::Tokenizer;

fn main() -> Result<(), Box<dyn std::error::Error>> {
  let tokenizer = Tokenizer::load_file("tokenizer.json")?;
  let ids = tokenizer.encode("Hello, world!", false)?;

  println!("{ids:?}");
  Ok(())
}

Rust returns the token IDs directly as a Vec<u32>. The boolean controls special-token insertion; use true to include them. For faster repeated loading, replace load_file() with load_file_with_st_cache().

Benchmarking and verifying correctness

Speed

Different tokenizer configurations exercise different parts of the implementation, so a speedup on GPT-2 alone tells us relatively little about performance elsewhere.

The main comparison covers twelve BPE tokenizers: GPT-2, GPT-OSS, Llama 3, Qwen 2.5, Qwen 3, DeepSeek R1, Gemma 3, GLM 4.7, MiniMax M2.1, Mistral Nemo, Nemotron 3, and Phi-4 Mini¹⁴. Together they cover a large variety of tokenizers, from GPT-2 with 50k vocab, and Gemma 3 with 262,144 vocab size, and a large variety of pre-tokenizers, and normalizers.

The data is Wikipedia text from enwik8

The main benchmark tests one 140-byte input, 32, and then 512 inputs of 140 bytes each, and a 4 KiB, 64 KiB, 1MiB and 4 MiB input.

Some useful data to look at:

For BPE, we found .st loading to be 9.33× faster than JSON on Apple ARM, 10.86× on AMD, and 9.73× on Intel. For Unigram, we achieved a 1.157× advantage net.

For Unigram, test processes twenty different LongBench contexts containing roughly eighteen million characters. We averaged 66.1× Hugging Face.

However I would like to note Gigatoken measures (I assume they optimize for as well, considering this is what they’re measuring) extremely large batch sizes of multiple GB. This is much more commonplace in training, RL, data prep, etc. rather than inference. For multi-gigabyte inputs of b=1 GigaToken wins by 2.49x

During inference, it is more common to see 3 to 4 digit input sizes (in bytes) and 4-digit batch sizes.

speed.mdis a frequently updated, agent-maintained doc discussing various speed information.

Correctness

Part of the CI is running 100% parity tests against hf tokenizers, on a large range of tokenizers. On bigger, hot path PRs, we test on different chipsets as well.

The main method of verifying correctness is fuzzers. Here are the ones we have written:

1. fuzz_encode: We feed arbitrary UTF-8 text into tokenizers. We run three with different splitting patterns, and one using ByteLevel pre-tokenization. Each input is encoded with special-token insertion both enabled and disabled.
2. fuzz_decode: It interprets input bytes as 32-bit token IDs, then decodes them with special tokens retained and skipped. We generate a large set of input bytes, and check for expected outputs.
3. fuzz_json_parse: Vary the tokenizer configuration, and generate vocabularies, merge lists, pre-tokenizers, decoders, added tokens, and byte-fallback settings, then calls Tokenizer::from_json(). We deliberately include negative tests, like processing WordPiece tokenizers. fuzz_json_parse does not test malformed JSON strings, we generate arbitrary serde_json::Value objects instead.
4. fuzz_roundtrip: We generate text, select a tokenizer, encode, then decode the result. We assert that decode(encode(text)) == text.
5. fuzz_st: A fuzz test that feeds deliberately garbage .st cache files to the loader and checks that it errors out instead of crashing.
6. fuzz_unigram: It makes the fuzzer invent random Unigram tokenizers and random inputs, then checks that the production encoder and a deliberately naive independent implementation produce identical token IDs.

How I use AI to make things fast

As a preface: I am no professional and am not an expert in what I am talking about. This represents my experience

I use AI very heavily in the development and maintenance of this project. I can confidently say ~90% of the code was written using AI, and ~100% of the code has been read and reviewed carefully.

I try to maintain a high bar for the code I am responsible for, to the best of my abilities.

I did auto research in two ways:

1. Broadly scoped: Early on, I could get away with telling the agent to repeatedly improve something fairly broad. Some examples:

hillclimb BPE pre-tokenization

improve low-batch speeds

Try to reduce the amount of branching

Find places we can do compiler optimizations, specifically marking how often used certain things are.

The goal of the things I said was to add as much human-style direction that agents would not find on their own.

Naturally, I experienced a lot of reward-hacking because of this, which I handled by manually reviewing the code, and cleaning it up. It helps to add fairly strict guardrails in the prompts I provided (clankers are pretty good at adding guardrails to your prompts). Running agents with fresh context to find reward-hacking works surprisingly well. ¹⁵

2. More narrow attempts: Later on, the agents started stalling and never getting anything done. At this point I had to start giving much more specific auto research goals. Some examples:

I bet we can start prefetching and maybe computing masks AoT during the scanners. Try that out and see how it goes

I am a bit worried about ARM CPUs, as I know they don’t support movemask. But the only reason we end up doing it is the algebra wants u64s, and we pay the fake movemask like 7x per block, one per class mask. see if we can merge or skip some collapses besides the apostrophe thing

Compare Aho-Corasick against other efficient implementations of string matching, and see if anything beats it. Do not compare in raw speed, but in the quality of the algorithm. If anything comes close, let me know. Bc the other implementations are probably not efficently written.

Construct .st files such that merged_id == rank + constant, or something adjacent to that, and see how it performs. Maybe each merge only needs its rank and position, since we can retrieve the left and right token IDs from the token sequence. Look at the way we compute bpe in-stack when the piece <=15 bytes, we use a similar trick. I want to try information packing tricks like this.

Besides these narrow, and deep auto-research attempts, we can also try broad and shallow ones:

Compare FxHashMap with HashMap in different circumstances throughout the codebase.

We use an index-based doubly linked list in MergeSymbol. Maybe this data structure has applications in other places.

Refactoring took a disproportionate share of the time, and was largely manual.

A trick I found really useful was keeping fully agent-maintained, detailed logs of every performance optimization we tried. It helps create intuition behind what optimization directions are worth looking into

Another trick I found useful (especially in broader optimization attempts), was specifying different ways the agent should approach finding optimizations.

Some examples:

“find traces of traditional CS algorithms in the codebase and find alternatives to those by reading academic research papers that maybe we can try.”

“do deep research online on ways people attempt different constructions of maps and see if that could apply to us”

“I read this technical blog: xxx. I don’t know where but this could potentially help us”

Oftentimes the things that restrict agents from finding more opportunities to optimize are that they tend to approach problems the same way every single time.

using a variety of models + harnesses helps as well.

My approach to refactoring with agents:

• Almost always, the implementation within a certain abstraction is decent ¹⁶, but the ways abstractions interact causes a majority of complexity.
• Provide the agents with access to a collection of useful software design and style guide books that they can query when making decisions.
• the same idea of just-hazy-human-intuition works for finding refactoring ideas¹⁷. Ask your clanker to: “find helpers that don’t contribute much” or “make sure all pre-tokenizers are available through a simple dispatcher”. A large majority of good refactoring is found manually still.
• naming almost always has to be decided manually. The way agents choose names for things is god-awful

Spending time on AGENTS.md proved substantially more useful than I thought, but I don’t have anything novel to say about it.

Links and references

• Github link and DeepWiki link. This blog is based off the codebase up to commit d8cff5f
• Some other really cool tokenizers: Gigatoken, Tokie, fastokens,riptoken, wordchipper hf tokenizers
• A very useful rust performance book

THANK YOU FOR READING!