Implement a BPE Tokenizer

Free with account Updated Nov 16, 2026 · 5 min read
On this page

    Problem statement

    Implement Byte Pair Encoding (BPE). Write train_bpe(word_counts, num_merges) that takes a dictionary of words and their frequencies and returns the ordered list of learned merges, where each merge joins the most frequent adjacent pair of symbols. Then write encode(word, merges) that splits a new word into tokens using those merges.

    A classic ML coding question for LLM roles: small enough for 45 minutes, and it shows whether you understand how tokenizers really work (see Tokens and Tokenization).

    Example

    Frequent endings like "est" and stems like "low" become single tokens; unseen words fall back to smaller pieces.
    Frequent endings like "est" and stems like "low" become single tokens; unseen words fall back to smaller pieces.
    corpus  = {"low": 5, "lower": 2, "lowest": 3, "newest": 6, "widest": 3}
    merges  = [('s','t'), ('e','st'), ('o','w'), ('l','ow'), ('w','est'), ('n','e')]
    encode("lowest") → ['low', 'est']
    encode("newer")  → ['ne', 'w', 'e', 'r']
    encode("slow")   → ['s', 'low']

    Constraints (assumed)

    • Up to about 100,000 distinct words; a few thousand merges in the interview version.
    • Characters as base symbols (byte-level is a follow-up).
    • Words are already split on whitespace; no special tokens.

    What this question tests

    • Translating the algorithm into clean data structures (tuples, counters, ranks).
    • Weighting pair counts by word frequency.
    • Deterministic tie-breaking, so training is reproducible.
    • Encoding consistently with training (merge order).

    Questions to ask first

    1. Characters or bytes as the base alphabet? (Characters here.)
    2. Is there an end-of-word marker? (Not here; it changes how suffixes merge.)
    3. How should ties be broken? (Any deterministic rule; state it.)
    4. Do I need decoding (ids back to text)? (Concatenating tokens is enough here.)
    5. Is efficiency important, or clarity first? (Clarity, then discuss speed-ups.)