How do you implement a BPE tokenizer from scratch?

In this article

1. Before you start
2. Why interviewers ask this
3. BPE tokenizer from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the PyTorch and machine learning (ML) coding round guide. It needs only basic Python.

Why interviewers ask this

Candidates report being asked to build byte-pair encoding from scratch in interviews at AI labs and in applied machine-learning roles. The task is short, has no heavy mathematics and exposes whether you understand the first stage of every language model pipeline.

A weak answer says "it merges common letters" and cannot write the loop. A strong answer states the training input, the pair-counting rule, the stop condition and what the output is: an ordered list of merges. A Staff-level answer adds the encoder's replay order, the byte-level base that removes unknown tokens, and the cost of the naive loop.

Byte-pair encoding was first built as a text-compression algorithm, and Hugging Face's course notes that OpenAI later used it to tokenize text for pretraining the GPT model. Sennrich et al. (2016) applied it to translation, so that rare and unknown words become sequences of subword units.

BPE tokenizer from first principles

BPE tokenizer

A BPE tokenizer is a text splitter that starts from single symbols, learns an ordered list of merge rules from the most frequent adjacent pairs in a training corpus, and encodes new text by applying those rules in the order they were learned.

Pre-tokenization

Pre-tokenization is the step that cuts raw text into word-like chunks before BPE runs, so that merges happen inside a chunk and never across two chunks.

In plain words

Picture a typist who keeps typing the same two letters together. After a while she buys a single key that types both. She keeps buying keys for the pairs she uses most, until the keyboard reaches a size she can afford. The analogy breaks here: a pair the tokenizer rarely saw gets no key, so rare words stay in smaller pieces.

In one precise sentence: BPE training starts from characters. It merges the most frequent adjacent pair again and again. It stops at a chosen vocabulary size. The vocabulary is the set of all symbols the tokenizer can output.

Step 1: Pre-tokenize the corpus and split each word into symbols

Pre-tokenization turns the corpus into a table of unique words and their counts. Hugging Face's course says the tokenizer normalizes and pre-tokenizes text before the model splits it into subtokens, and its BPE chapter starts training from the unique words of the corpus. The base vocabulary is every symbol used to write those words.

Input: raw text. Output: a dictionary from word to count, and each word written as a list of single symbols. In the worked example below the toy corpus has four words with the illustrative counts 5, 2, 6 and 3, and ten base symbols.¹ You now have the data the loop works on: weighted words made of symbols.

Step 2: Count adjacent pairs, weighted by word frequency, and merge the top one

For every word, look at each neighbouring pair of symbols and add the word's count, not one, to that pair's total. Counting each distinct word once is the common error: it treats a word seen once like a word seen a thousand times and can pick different merges. On the toy corpus, counting each word once keeps the first four merges but makes merge 5 d+est instead of e+w.¹

Input: the word table. Output: one pair chosen. In the toy corpus the pairs e+s and s+t each total 9, because "newest" contributes 6 and "widest" contributes 3.¹ A tie like that needs a rule; the loop here picks the smaller pair in alphabetical order, so e+s wins.

Then merge: scan each word and replace every occurrence of the chosen pair with one new symbol. Record the pair in the merge list. A merge can create new pairs, such as es+t, and the next count sees them. You now know one full round of training.

Step 3: Repeat until the vocabulary reaches the target size

The loop runs once per merge, and every merge adds exactly one symbol, so the number of merges is the target vocabulary size minus the base vocabulary size. With ten base symbols and a target of 17, the loop runs seven times.¹ A real tokenizer works the same way with a far larger target.

Input: the word table after the previous merge. Output: a longer merge list and a bigger vocabulary. Stop early if no pairs remain, which happens when every word has become one symbol. The final output of training is not the text: it is the ordered merge list plus the base vocabulary. Hugging Face states that its code is a teaching version that is not optimized for a big corpus, and the same is true of the code on this page. Next you use the list to encode.

Step 4: Replay the merges in training order to encode text

To encode a new word, split it into base symbols, then apply every merge rule in the order it was learned. Order matters because a later rule is defined on symbols an earlier rule created. Applying es+t before e+s finds nothing to merge.

Input: one pre-tokenized word and the merge list. Output: a list of tokens. Sennrich et al. (2016) use BPE in the same way to segment rare words into subword units. For the unseen word "lowest" the replay gives low and est, two tokens, although "lowest" never appeared in training.¹ That is the point of subword units: new words are built from known pieces.

1 · Words and counts2 · Count and merge3 · Repeat4 · EncodeReplay

Step-by-step description

1. Pre-tokenize into weighted words.
2. Weight pairs by word count, merge the top.
3. Each merge adds one vocabulary entry.
4. Replay the merges in training order.

• Training starts from a table of words and their counts.
• Pair counts are weighted by word frequency and the top pair is merged.
• The merge list is ordered, and encoding replays it in training order.

Worked example

The corpus is illustrative: the words low, lower, newest and widest with counts 5, 2, 6 and 3. The base vocabulary is the ten letters d, e, i, l, n, o, r, s, t and w. The top five starting pair counts are e+s 9, s+t 9, w+e 8, l+o 7 and o+w 7.¹ The pairs e+s and s+t each occur 9 times. The pair w+e occurs 8 times, and l+o and o+w occur 7 times each.

Text description of the diagram

• The pairs e+s and s+t each occur 9 times.
• The pair w+e occurs 8 times, and l+o and o+w occur 7 times each.

The numbers in the table are computed.¹ After merge 4, "low" is a single token, and "widest" ends as w / i / d / est. Encoding the unseen word "newer" replays the list: only merge 5 applies, giving n / ew / e / r, four tokens.¹

The code below is the whole algorithm. merge_pair replaces a pair inside one word, train_bpe returns the ordered merge list, and encode replays it.

from collections import Counter

def merge_pair(symbols, pair):
    out, i = [], 0
    while i < len(symbols):
        if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
            out.append(symbols[i] + symbols[i + 1])  # join the pair
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return out

def train_bpe(word_counts, num_merges):
    words = {w: list(w) for w in word_counts}
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for w, symbols in words.items():
            for a, b in zip(symbols, symbols[1:]):
                pairs[(a, b)] += word_counts[w]  # weight by word frequency
        if not pairs:
            break
        best = min(pairs, key=lambda p: (-pairs[p], p))  # tie: smaller pair
        merges.append(best)
        words = {w: merge_pair(s, best) for w, s in words.items()}
    return merges

def encode(word, merges):
    symbols = list(word)
    for pair in merges:  # replay in training order
        symbols = merge_pair(symbols, pair)
    return symbols

def build_vocab(base, merges):
    # ids: base symbols first, then one id per merge in training order
    return {tok: i for i, tok in enumerate(base + [a + b for a, b in merges])}

def decode(ids, vocab):
    inverse = {i: tok for tok, i in vocab.items()}
    return "".join(inverse[i] for i in ids)

# byte-level start for a word: list("héllo".encode("utf-8"))

Training also gives each token an integer id, its position in the list of base symbols followed by the merges in order. Here base is sorted({c for w in word_counts for c in w}). In the toy run "lowest" encodes to low and est, ids 13 and 11, and decode joins the strings back into "lowest".¹ With a byte base the starting point is list(word.encode("utf-8")), which gives 104, 195, 169, 108, 108, 111 for "héllo".¹ Decoding then joins the bytes and calls .decode("utf-8", errors="replace"). The replacement matters because one character can span several tokens and a generated byte sequence may be invalid: a lone byte 195 decodes to the Unicode replacement character instead of raising an error.¹

Each training round scans every word, so the naive cost is about the number of merges times the corpus size, which is why production tokenizers use faster bookkeeping. Likewise encode replays every merge, so its cost is the number of merges times the word length; production encoders instead repeatedly merge the lowest-rank (earliest-learned) pair present in the word. The min call with a negated count breaks ties the same way on every run; a different tie rule gives a different merge list, so fix one and state it.

Trade-offs and edge cases

The base vocabulary is the main design choice. With a character base, Hugging Face notes that a character absent from the training corpus becomes the unknown token. With a byte base, called byte-level BPE, the base vocabulary has 256 symbols and every character can still be written; the same page says GPT-2 and RoBERTa work this way. The cost is length: the letter é takes one symbol with a character base but two bytes in UTF-8, so the toy word "héllo" has five characters and six UTF-8 bytes.¹

Text description of the diagram

• A character base turns a character missing from the corpus into the unknown token.
• A byte base has 256 symbols and covers every character.
• The letter é takes two bytes in UTF-8.

Pre-tokenization is the second choice. Merges happen inside pre-tokenized words, so where you cut decides what can ever merge. GPT-2's pre-tokenizer keeps each space attached to the start of the next word, and its byte-to-character mapping prints that space as Ġ, so "Hello, how" becomes 'Hello', ',', 'Ġhow' (Hugging Face).

Third, BPE is not the only subword algorithm. Hugging Face lists BPE, WordPiece (used by Bidirectional Encoder Representations from Transformers (BERT)) and Unigram (used by T5), so "all language models use BPE" is wrong. Fourth, the toy loop here ignores normalization such as lowercasing; a real tokenizer decides that first, and the decision changes the counts. Tokenization sits before everything in a model: the positional encodings and attention layers later operate on the token sequence this step produces.

How to answer it in an interview

The spoken structure: say the input, the counting rule, the stop condition, the encoder's replay order, then the trade-off of the base vocabulary.

Common mistakes

• "I count each unique word once." (wrong) Pair totals must add the word's frequency. (right) "I weight every pair by the count of the word it comes from."
• "To encode, I look for the longest matching token." (wrong) That is a different algorithm and can disagree with training. (right) "I replay the merges in the order they were learned."
• "BPE merges across spaces." (wrong) Pre-tokenization cuts the text first. (right) "Merges happen inside pre-tokenized words."
• "My vocabulary size is the number of merges." (wrong) The base symbols count too. (right) "Merges equal target size minus base size."
• "Ties don't matter." (wrong) A tie decides the first merge in the toy corpus and so changes the whole list. (right) "I fix a deterministic tie rule."

Follow-up questions

How do I implement a BPE tokenizer in Python without a library?

Write three functions: one that merges a pair inside a list of symbols, one that trains by counting pairs weighted by word frequency, and one that encodes by replaying the merge list. The code above is complete for the toy case.

How do you encode new text after training?

Pre-tokenize it, split each word into base symbols, and apply every merge rule in training order. A word never seen in training still encodes, as "lowest" becomes low and est in the worked example.¹

How do you decode tokens back to text?

Map each id back to its token string and join the strings. With a byte base, join the bytes first and decode the result as UTF-8 with errors replaced, because one character can span several tokens and a generated byte sequence may be invalid.

How do you tokenize 3D trajectory data so you can predict the next step?

Candidates report this question for a self-driving-company round. A reasonable approach, offered as advice: convert each position to the change from the previous point, divide each coordinate's range into bins, treat each bin id as a token, and train a model to output the next token. The idea is to discretize continuous values; merging frequent token pairs is optional.

How would you split LLM input into token-sized queues?

Tokenize the text first, then slice the token list into chunks of at most a fixed length and queue the chunks in order. Chunk on token counts, not characters, because the model's limit is counted in tokens. Candidates report a version of this with an existing class to complete.

Does every language model use BPE?

No. Hugging Face names WordPiece for BERT and Unigram for T5 as the other two main algorithms. After tokenizing, decoding strategies such as beam search and the numerically stable softmax work on the token probabilities, and the causal mask controls what each token may see.

Sources

1. Neural Machine Translation of Rare Words with Subword Units (arXiv 1508.07909) — arXiv (Sennrich, Haddow, Birch), 10 Jun 2016
2. Byte-Pair Encoding tokenization, LLM Course chapter 6.5 — Hugging Face (read 2026-10-26; undated page), 26 Oct 2026
3. Normalization and pre-tokenization, LLM Course chapter 6.4 — Hugging Face (read 2026-10-26; undated page), 26 Oct 2026