On this page
How does a tokenizer get its vocabulary? Byte Pair Encoding (BPE), byte-level BPE, WordPiece and Unigram each build a fixed list of pieces once, from a large training text called a corpus, and then split every new text with it. SentencePiece is the toolkit that runs BPE or Unigram on raw text. They differ in how the pieces are chosen: BPE and WordPiece grow the list by merging (byte-level BPE is BPE run on bytes), and Unigram shrinks a big list by pruning.
A token is one piece of text, its token id is its position in the vocabulary, V is the number of vocabulary entries and T the number of tokens in one input, as in Tokenizers. Turning text into ids is encoding; turning ids back into text is decoding. A bigger V holds longer pieces, so the same text needs a smaller T (how big the vocabulary should be). A word-level vocabulary maps every word it lacks to one unknown token, <unk>. UTF-8 writes every character as 1 to 4 bytes, and a byte has only 256 values.
Each algorithm runs once, on the corpus, before the model is trained, and saves a fixed file (when a tokenizer runs). Encoding replays that file on every text and keeps no state between calls; only optional sampling (Section 4.3), which exists for both Unigram and BPE, changes the split from call to call, and only while the model trains.
How do you build a vocabulary from the bottom up? Start from single characters, merge the adjacent pair that appears most often into one new token, and repeat a fixed number of times. Sennrich, Haddow and Birch (2016) brought BPE to tokenization, taking the idea from a 1994 compression method by Gage that replaces the most frequent pair of bytes with an unused byte.
BPE first counts how often each word appears, so a corpus becomes a short list of words with their frequencies. The BPE paper also ends each word with a special end-of-word symbol, which this page’s toy leaves out.
Count every adjacent pair, merge the most frequent one, repeat.
u g is the most frequent pair (1), so ug becomes one token everywhere (2). Data from Reference 10.The line of the card in Section 1.1 that this step runs.
b un could still merge. Each merge added one entry, so the vocabulary has 13.Figure 3. Toy corpus. Each step merges the pair with the tallest bar, marked next, into one token.
Code 1 is the equation card in Section 1.1 as code. It learns the first three merges of the toy corpus.
from collections import Counter
def merge(symbols, pair):
out, i = [], 0
while i < len(symbols):
if symbols[i:i + 2] == pair:
out.append(symbols[i] + symbols[i + 1])
i += 2
else:
out.append(symbols[i])
i += 1
return tuple(out)
def train_bpe(word_freqs, num_merges):
words = {tuple(w): f for w, f in word_freqs.items()}
merges = []
for _ in range(num_merges):
pairs = Counter()
for symbols, f in words.items():
for pair in zip(symbols, symbols[1:]):
pairs[pair] += f
best = max(pairs, key=pairs.get)
merges.append(best)
words = {merge(symbols, best): f for symbols, f in words.items()}
return merges, words
corpus = {"hug": 10, "pug": 5, "pun": 12, "bun": 4, "hugs": 5}
merges, words = train_bpe(corpus, 3)
print(merges) # [('u', 'g'), ('u', 'n'), ('h', 'ug')]
print(words) # {('hug',): 10, ('p', 'ug'): 5, ('p', 'un'): 12, ('b', 'un'): 4, ('hug', 's'): 5}merge replaces every adjacent copy of the pair with one symbol.f.max takes the most frequent pair, the first found on a tie.To split a word, start from its characters and replay the merges in the order they were learned. A character never seen in training, such as a rare script or an emoji, has no starting symbol, so character BPE still needs <unk>.
Code 2 splits two words that are not in the toy corpus, using the merges from Code 1. The second word starts with m, a letter the corpus never had.
def encode(word, merges, alphabet):
symbols = tuple(c if c in alphabet else "<unk>" for c in word)
for pair in merges:
symbols = merge(symbols, pair)
return symbols
alphabet = set("".join(corpus)) # h, u, g, p, n, b, s
print(encode("bugs", merges, alphabet), encode("mug", merges, alphabet)) # ('b', 'ug', 's') ('<unk>', 'ug')<unk>.bugs splits into known pieces; m was never seen, so mug keeps only ug.
GPT-2 (Radford et al., 2019) runs BPE on UTF-8 bytes instead of characters. The starting alphabet is exactly 256 symbols, against more than 130,000 Unicode characters, so every string can be encoded and no <unk> exists. GPT-2 has 256 bytes plus 50,000 merges plus one end-of-text token, a special token that marks where a document ends, 50,257 entries (Reference 10). The cost is that a rare character can be cut into byte pieces that are not text on their own, the hatched cells of the one string, many vocabulary sizes tool, and scripts other than English need more tokens for the same text (other languages cost more tokens).
OpenAI’s tiktoken encodings, such as cl100k_base and o200k_base, are byte-level BPE vocabularies; the list of what current models use shows which model uses which.
Before merging, a regular expression cuts the text into chunks of one character category, such as letters, digits or punctuation, and keeps a single space on the front of the next chunk. Merges never cross a chunk border. Without this, the GPT-2 paper reports, BPE learned many copies of one word with punctuation attached, such as dog., dog! and dog?.
WordPiece merges bottom up like BPE but picks a different pair. Schuster and Nakajima (2012) introduced it; Google’s translation system (Wu et al., 2016) and BERT (Devlin et al., 2019, 30,000 tokens) used it. The idea is to merge pieces that belong together, not just pieces that are common. Pieces inside a word carry the prefix ##. Google never published its training code, so the training here is Hugging Face’s reconstruction (Reference 12).
The pair count divided by the counts of both parts.
u g (1); WordPiece merges ##g ##s, because s only ever appears after g (2). Data from References 10, 12.
To split new text, WordPiece does not replay merges. It takes the longest vocabulary entry that matches the start of the word, then the longest ## entry for the rest, and so on. If nothing matches, the whole word becomes BERT’s unknown token, [UNK]. bert-base-uncased splits antidisestablishmentarianism into anti ##dis ##est ##ab ##lish ##ment ##arian ##ism.
Unigram (Kudo, 2018) works the other way round. It starts from a large list of candidate pieces, every character plus the corpus’s most frequent substrings, gives each a probability, and removes the pieces that help least until the target size is left.
One word can be split many ways, and each piece has a probability.
Score a split by multiplying its piece probabilities, then keep the best split.
Training repeats one loop until V pieces are left: fit the piece probabilities to the corpus, then drop the pieces the corpus misses least. The seed list is found with a suffix array, a sorted index of every substring; SentencePiece keeps 1,000,000 of them by default, seed_sentencepiece_size (Reference 13).
Fit the probabilities to the corpus, then drop the pieces the corpus misses least.
shrinking_factor defaults to 0.75 (References 4, 13). A higher η prunes gently over more rounds; a lower one prunes hard in few rounds.The weakness is training cost. Each round runs EM over the whole corpus and then recomputes the likelihood L without each piece to get its loss Δi, where BPE only counts adjacent pairs.
While the model trains, the Unigram paper samples a different split of each word every time instead of always the best. The model sees varied splits and becomes more robust; the paper calls this subword regularization. Sampling is for training only: when the trained model is used, the tokenizer returns the single best split x*.
Each split’s chance of being drawn, sharpened by α.
Figure 8. Toy. The three splits of hugs from Figure 6; bar length is the chance of being drawn.
BPE can sample too. BPE-dropout (Provilkov, Emelianenko and Voita, 2020) keeps the merge list but skips each possible merge with a probability p while splitting a word, and uses plain BPE once training is done. Raising p gives more and shorter pieces: p = 0 is plain BPE and p = 1 leaves single characters; the paper uses p = 0.1 for most languages, and SentencePiece’s alpha sets this p for a BPE model. SentencePiece runs both through the same enable_sampling option (References 15, 16).
SentencePiece (Kudo and Richardson, 2018) is a toolkit, not a new algorithm: it trains and runs BPE or Unigram, Unigram by default. It does not cut text on spaces first. The space is an ordinary symbol, ▁, so decoding the tokens gives back the text exactly, spaces included, after one cleanup step described next. This matters for languages written without spaces.
In training and every time it encodes, it rewrites look-alike characters into one standard form. The default rule, nmt_nfkc, builds on Unicode NFKC, the standard rule that turns a full-width Ａ into A and the ligature fi into fi (Reference 13). This is SentencePiece’s weakness: decoding gives back the rewritten text, so Ａ comes back as A, and without byte fallback a character outside the vocabulary becomes <unk>.
Two switches change how text is split. Byte fallback writes a character missing from the vocabulary as its UTF-8 bytes instead of <unk>, and digit splitting makes every digit its own token. Llama 2 and Gemma turn both on, and Gemma also keeps runs of spaces instead of collapsing them (References 8, 9).
character_coverage is the share of the corpus’s characters the vocabulary must cover; rarer characters fall to <unk> or to bytes. The default 0.9995 suits large character sets such as Chinese and Japanese, and 1.0 suits small alphabets such as English (Reference 13).
▁ (1), so the spaces can be rebuilt exactly; the numbers under the best split are its ids, and sampling varies the split (2). Data from Reference 14.You train a vocabulary once, on text that looks like what the model will read, and every later step depends on it. The official code lives in Hugging Face tokenizers and SentencePiece.
Training reads the whole corpus into memory by default; for a large corpus, input_sentence_size trains on a random sample of that many sentences instead (Reference 13). Unigram is the pick when you want each sampled split drawn by its probability (Section 4.3); byte-level BPE is the pick when no text may ever be unknown.
Code 3 trains a small Unigram vocabulary on corpus.txt, any plain text file with one sentence per line, then splits a string twice.
import sentencepiece as spm
spm.SentencePieceTrainer.train(
input="corpus.txt",
model_prefix="tok",
vocab_size=8000,
model_type="unigram",
character_coverage=0.9995,
byte_fallback=True,
split_digits=True,
)
sp = spm.SentencePieceProcessor(model_file="tok.model")
print(sp.encode("This is a test", return_type=str))
print(sp.encode("This is a test", return_type=str,
enable_sampling=True, alpha=0.1, nbest_size=-1))| Setting | Raise or on | Lower or off | Default |
|---|---|---|---|
vocab_size (V), vocabulary size | shorter T, bigger table; very large keeps whole words | longer T, smaller table; just above the character count leaves single characters | 8000 [13]; models 30K to about 262K |
character_coverage, Section 5 | keeps rarer characters; 1.0 keeps all | more characters fall to <unk> or bytes | 0.9995 [13] |
byte_fallback, Section 5 | a missing character becomes UTF-8 bytes | it becomes <unk> | off [13]; on in Llama 2, Gemma [8, 9] |
split_digits, how numbers split | one token per digit | learned digit runs stay | off [13]; on in Llama 2, Gemma [8, 9] |
shrinking_factor (η), Section 4.2 | prunes gently over more rounds; near 1 barely prunes | prunes hard in few rounds | 0.75 [13]; paper 0.8 [4] |
alpha (α), Section 4.3 | Unigram: closer to the best split; BPE: alpha is the dropout probability, so more pieces | Unigram: closer to even, 0 makes all splits equal; BPE: fewer skipped merges | none; 0.1 in the README [14] |
The model’s last layer gives one score for each of the V entries at every step. How does it turn those scores into the next id? Softmax, Temperature and Decoding answers that; there, decoding means choosing the next token, and the tokenizer then turns the chosen ids back into text.
alpha is the dropout probability for BPE.