Tokenizers From Scratch, and What Happens When You Add a Token

Tokenization is a design choice

Before a model sees text, a tokenizer cuts it into pieces and maps each piece to an id. There is no single "correct" way to do the cutting. We will focus on two dominant approaches in this cookbook. The first one is greedy longest match , which scans left to right and takes the longest piece in the vocabulary at each step. The second is Byte pair encoding , which applies a ranked list of learned merges, building pieces from the bottom up. These are not two implementations of the same idea; they can segment the same word into different tokens, and that difference propagates into how long your sequences are and what your model learns. The clearest way to see this is to build both and run them against each other, which is short enough to do from scratch.

Greedy Longest Match

The first tokenizer can be implemented in multiple ways, but an efficient one keeps a vocabulary of pieces in a trie (a tree-like data structure) and, from each position in the text, walks the trie as far as it can, preserving the longest piece that formed a valid token along the way. As long as every single character is in the vocabulary, the encoder always makes progress and the decoder is just concatenation.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.token_id = None

class Tokenizer:
    def __init__(self, vocab):                       # vocab: {piece_string: id}, includes every character
        self.vocab = vocab
        self.inv   = {i: t for t, i in vocab.items()}
        self.root  = TrieNode()
        for piece, tid in vocab.items():
            node = self.root
            for ch in piece:
                node = node.children.setdefault(ch, TrieNode())
            node.token_id = tid

    def encode(self, text):
        ids, i, n = [], 0, len(text)
        while i < n:
            node, last_id, last_len = self.root, None, 0
            for j in range(i, n):                    # walk the trie from position i
                if text[j] not in node.children:
                    break
                node = node.children[text[j]]
                if node.token_id is not None:        # a complete piece ends here
                    last_id, last_len = node.token_id, j - i + 1
            if last_id is not None:
                ids.append(last_id); i += last_len   # take the longest piece found
            else:
                ids.append(self.vocab[text[i]]); i += 1   # fall back to the single character
        return ids

    def decode(self, ids):
        return "".join(self.inv[i] for i in ids)

With a small vocabulary of a few subwords plus every character it needs, it tokenizes and reconstructs a sentence cleanly.

pieces = ["token", "ization", "fine", "tun", "ing", "the", " "]
chars  = sorted(set("the tokenization fine tuning"))
vocab  = {t: i for i, t in enumerate(pieces + chars)}

mm = Tokenizer(vocab)
ids = mm.encode("the tokenization fine tuning")
print("pieces:", [mm.inv[i] for i in ids])
print("round-trip ok:", mm.decode(ids) == "the tokenization fine tuning")

pieces: ['the', ' ', 'token', 'ization', ' ', 'fine', ' ', 'tun', 'ing']
round-trip ok: True

Note that the domain word "tokenization" was not in the vocabulary, so it split into "token" and "ization." Hold onto that; it is the seam the new-token discussion will pull on.

Byte Pair Encoding

Byte pair encoding works differently. Training starts from the text as individual characters and repeatedly does one thing: count every adjacent pair of symbols across the corpus, merge the single most frequent pair into a new symbol, and record that merge. After a few hundred rounds the recorded merges, in the order they were learned, are the entire tokenizer. Encoding a new word then replays those merges by rank, always applying the earliest-learned merge that fits, until none apply.

from collections import Counter

def train_bpe(words, num_merges):
    freq   = Counter(words)
    splits = {w: list(w) for w in freq}              # every word starts as its characters
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for w, f in freq.items():
            s = splits[w]
            for a, b in zip(s, s[1:]):
                pairs[(a, b)] += f                    # count adjacent pairs, weighted by word frequency
        if not pairs:
            break
        best = max(pairs, key=lambda p: (pairs[p], p))   # most frequent pair (deterministic tie-break)
        merges.append(best)
        a, b = best
        for w, s in splits.items():                  # apply the merge everywhere
            out, i = [], 0
            while i < len(s):
                if i < len(s) - 1 and s[i] == a and s[i + 1] == b:
                    out.append(a + b); i += 2
                else:
                    out.append(s[i]); i += 1
            splits[w] = out
    return merges

def bpe_encode(word, merges):
    s    = list(word)
    rank = {pair: i for i, pair in enumerate(merges)}
    while len(s) > 1:
        best = min(((rank[p], p) for p in zip(s, s[1:]) if p in rank), default=None)
        if best is None:
            break                                    # no learned merge applies; we are done
        a, b = best[1]
        out, i = [], 0
        while i < len(s):
            if i < len(s) - 1 and s[i] == a and s[i + 1] == b:
                out.append(a + b); i += 2
            else:
                out.append(s[i]); i += 1
        s = out
    return s

The training loop can be inspected to show how the merges form, each one the most common pair given the merges already made.

Where The Two Differ

These two methods are not interchangeable, and the easiest way to see it is to give them the exact same vocabulary and find an input they split differently. We can engineer one deliberately. Train BPE on a corpus where it learns to merge the pair "a,b" first, then "c,d," and only then "ab,c" into "abc." Now take the set of pieces BPE can produce as the vocabulary, hand it to first tokenizer, and tokenize the string "abcd" with both.

corpus = ["ab"] * 3 + ["cd"] * 4 + ["abc"] * 2          # makes BPE learn ab, then cd, then abc
merges = train_bpe(corpus, num_merges=3)
print("merges, in rank order:", merges)

# the vocabulary BPE can build: every character, plus every merged piece
vocab_set = set("".join(corpus)) | {a + b for a, b in merges}
mm_vocab  = {t: i for i, t in enumerate(sorted(vocab_set))}
mm        = MaxMatchTokenizer(mm_vocab)

print("BPE     'abcd' ->", bpe_encode("abcd", merges))
print("MaxMatch 'abcd' ->", [mm.inv[i] for i in mm.encode("abcd")])

merges, in rank order: [('a', 'b'), ('c', 'd'), ('ab', 'c')]
BPE     'abcd' -> ['ab', 'cd']
MaxMatch 'abcd' -> ['abc', 'd']

Same vocabulary, same input, two different segmentations. BPE follows its merge ranks: it merges "a,b" and "c,d" because they were learned first, and arrives at "ab" plus "cd." The greedy one ignores ranks entirely and grabs the longest piece it can from the left, which is "abc," leaving a stranded "d." Neither is wrong, and, tellingly, neither is trying to minimize the number of tokens. Greedy longest match has no lookahead, so its first long grab can strand a worse remainder; BPE is simply executing a recipe of merges that was fit to a corpus. This is why a third family exists, the Unigram model used by SentencePiece, which scores whole segmentations probabilistically and uses a Viterbi search to pick the most likely one rather than a greedy one; we will not build it, but it is a principled answer to a notion of optimality both of these methods give up.

Why The Difference Matters

The segmentation a tokenizer chooses sets the number of tokens a given text becomes, and that number is the unit of almost everything downstream. It is the length of the sequence, so it drives the compute and memory of every forward pass and the size of the context you can fit. It is also what the model has to model: a word delivered as one token is one thing to learn, while the same word shattered into five pieces is a five-step pattern the model must reassemble. Two tokenizers that disagree on your domain's vocabulary will, on the same data and the same model, produce different sequence lengths and present different learning problems.

Adding a Token: Easy Half

Suppose your domain leans hard on a word the base vocabulary fragments, "tokenization," and you want it to be a single token. For Greedy Longest Match this is trivial: drop the string into the vocabulary and the longest-match rule picks it up on the next encode, with no retraining of the tokenizer at all.

base  = {t: i for i, t in enumerate(["token", "ization", "fine", "tun", "ing", "the", " "] +
                                    sorted(set("the tokenization fine tuning")))}
text  = "the tokenization fine tuning"

before = Tokenizer(base)
print("before:", [before.inv[i] for i in before.encode(text)])

base["tokenization"] = len(base)                       # add one domain token
after = Tokenizer(base)
print("after :", [after.inv[i] for i in after.encode(text)])

before: ['the', ' ', 'token', 'ization', ' ', 'fine', ' ', 'tun', 'ing']
after : ['the', ' ', 'tokenization', ' ', 'fine', ' ', 'tun', 'ing']

Two tokens became one, and it seems like an improvement. However on the flip side: adding tokens for strings that are rare, and you have enlarged the vocabulary, and therefore the embedding matrix, for almost no reduction in sequence length. The decision to add a token is an efficiency trade off, not a free improvement.

Token Addition in BPE

BPE makes the same request more complicated. BPE can only produce tokens its merge rules know how to build, so a genuinely new string is not reachable: there is no merge that ends at it. You cannot simply append "tokenization" to a BPE vocabulary and expect it to appear, because the encoder never consults a list of whole tokens, only the ranked merges. This is exactly why real tokenizers keep a separate added-tokens table that is matched before the model's BPE runs at all. The text is first cut at any added or special tokens, as exact strings by longest match, and BPE is applied only to the gaps between them. For example, Hugging Face's tokenizers describe this plainly: added tokens are handled independently of the underlying structure and are kept from being split during tokenization. In other words, the added-token path is precisely the Greedy Longest Match trie from the start of this piece, bolted onto the front of BPE.

def encode_with_added(text, added, merges):
    added = sorted(added, key=len, reverse=True)       # longest added token wins
    out, i, n, gap = [], 0, len(text), ""
    def flush():
        nonlocal gap
        for w in gap.split(" "):
            if w: out.extend(bpe_encode(w, merges))     # BPE only ever sees the gaps
        gap = ""
    while i < n:
        hit = next((a for a in added if text.startswith(a, i)), None)
        if hit:
            flush(); out.append(hit); i += len(hit)     # the added token is emitted whole
        else:
            gap += text[i]; i += 1
    flush()
    return out

merges = train_bpe("the fine tuning model token the the fine model".split(), 6)
print("BPE alone on a control token:", bpe_encode("<user>", merges))
print("with an added-tokens table  :", encode_with_added("hi <user> there", {"<user>"}, merges))

BPE alone on a control token: ['<', 'u', 's', 'e', 'r', '>']
with an added-tokens table  : ['h', 'i', '<user>', 'the', 'r', 'e']

Left to BPE, the control token "<user>" shatters into six characters, which is useless if you meant it as one indivisible marker. Registered as an added token, it is matched first and emitted whole, and BPE only touches the ordinary text around it. This is the mechanism behind every chat template token and every sentinel you have ever added to a model, and it closes the loop between the two tokenizers we built: you learned BPE for the base vocabulary and Greedy Longest Match for the pieces, and the way you add tokens for fine-tuning is to run Greedy Longest Match over BPE.

A Harder Part: Embeddings

Getting the tokenizer to emit your new token is the easy piece. The part that actually causes common issues like "I added a token and the model got worse" is on the model side. A new token gets a new id at the end of the vocabulary, which means the embedding matrix has to grow by a row, and that new row is initialized to noise. The model has never seen it and has no representation for it, so until you train that row, the token carries no meaning and degrades the outputs wherever it appears. The standard fix is not to leave it random but to initialize it as the average of the embeddings of the subword tokens it used to split into, an idea that goes back to Welch and colleagues in 2020 and Hewitt in 2021. The new row then starts in the right neighborhood, correlated with its own parts rather than pointing nowhere.

import numpy as np
rng = np.random.default_rng(0); d = 16
base = ["token", "ization", "fine", "tun", "ing", "the", "model"]
emb  = {t: rng.normal(size=d) for t in base}            # pretend pretrained embeddings

pieces      = ["token", "ization"]                      # how "tokenization" used to split
random_init = rng.normal(size=d)                        # what resize gives you by default
mean_init   = np.mean([emb[p] for p in pieces], axis=0) # average of the subword rows

cos = lambda a, b: float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))
print("random row vs its parts:", round(cos(random_init, emb["token"]), 2),
                                   round(cos(random_init, emb["ization"]), 2))
print("mean   row vs its parts:", round(cos(mean_init,   emb["token"]), 2),
                                   round(cos(mean_init,   emb["ization"]), 2))

random row vs its parts: 0.19 0.36
mean   row vs its parts: 0.85 0.72

The mean-initialized row starts strongly aligned with the subwords it came from, while the random row is essentially unrelated to anything. A practical refinement, when the model has a separate output projection, is to initialize the output row not with the average but with the embedding of the first subword, which tends to work better for the unembedding. Either way, initialization only gives the new token a sensible starting point; it still has to be trained. The mechanics of training just those rows, including the tied-weight and adapter subtleties, are the subject of the custom-token cookbook, and this is the natural handoff to it.

Pitfalls with New Tokens

A few failures recur often enough. The most common is the tokenizer and the model falling out of sync: you add tokens to the tokenizer but forget to resize the model's embeddings, and the new ids index past the end of the matrix, or you resize and forget that the output projection is a separate matrix that also needs the new row. There is the leading-space trap, where in many tokenizers a word and the same word with a space in front are different tokens, so an added token without the expected space boundary never matches the text you meant it to. There is the special token that gets split because it was added as ordinary text rather than registered as a token to protect from splitting. And there is the quiet cost of enthusiasm: every added token is another row of the embedding and output matrices, vocabulary size times hidden dimension in parameters each, so a few thousand speculative tokens is a real allocation for a benefit you may not be getting.

When to Add Tokens

The honest default is that most fine-tuning needs no new tokens at all. A model can already spell your domain's words out of existing subwords, and fine-tuning teaches it the behavior you want on top of that representation without touching the vocabulary. The cases where adding tokens earns its keep are narrower than people expect. One is efficiency: a string that appears constantly in your data and fragments into many pieces is worth a single token, because the sequence-length saving compounds across every example. The other is control: chat-template markers, tool-call delimiters, and sentinels that must be single, indivisible, never-split units have to be added tokens, because there is no other way to guarantee they survive tokenization whole. Outside those, the safe move is to reach for new tokens last, not first.

Where This Departs From Production

The two algorithms here are the real ones, but production tokenizers wrap them in machinery we left out. Modern BPE runs on raw bytes rather than characters, so it never has to fall back to an unknown token, and it is preceded by a regular-expression pre-tokenizer that decides where words and whitespace break before any merging happens, which is where the leading-space behavior comes from. SentencePiece treats the input as a raw stream, spaces included, and offers both BPE and the Unigram model. There is a normalization step before all of it, and the whole pipeline in libraries like Hugging Face's tokenizers is implemented in Rust for speed. None of that changes the substance you have here: a vocabulary of pieces, an algorithm that chooses among them, and an added-tokens layer matched first for the tokens you introduce yourself.

Common questions

Is BPE just longest match?

No, the example above is the proof. BPE applies its learned merges in rank order, which can produce a different segmentation than greedy longest match would over the same vocabulary, as "abcd" splitting into "ab" and "cd" rather than "abc" and "d" shows. Longest match is the rule in WordPiece; merge rank is the rule in BPE. Treating them as the same thing is the single most common tokenizer misconception.

Do I need to add tokens to fine-tune on my domain?

Usually not. The model can represent your domain's words through existing subwords, and fine-tuning adjusts its behavior without any vocabulary change. Add tokens only for strings frequent enough that the sequence-length saving is worth a new embedding row, or for control and special tokens that must never be split. For ordinary domain adaptation, changing the vocabulary is rarely the thing that helps.

I added a token and the model produces garbage. Why?

Almost always because the new token's embedding is untrained. Adding the token to the tokenizer makes it appear in the input ids, but its embedding row started as noise, so the model has no meaning for it. Initialize the row from the average of the subwords it used to split into, make sure you resized both the input embedding and the output projection, and then train the new rows. The token will keep producing nonsense until that row has been learned.