Explain BPE (Byte Pair Encoding).

In this question, we will learn BPE (Byte Pair Encoding) from first principles and see a worked example so you can explain both the algorithm and its practical tradeoffs. We will keep the math light and focus on how merges change tokens and probability of token sequences.

We will cover the following:

• The intuition
• How it actually works
• Choosing vocabulary size and merges
• Tradeoffs and failure modes
• Questions the interviewer might ask
• What the interviewer is really testing

Direct answer: BPE is a greedy subword tokenization algorithm that starts from single characters and repeatedly merges the most frequent adjacent symbol pair to build a vocabulary. It yields a compact token set where common substrings are tokens and rare words are split, which balances vocabulary size and tokenization length. Training performs $M$ merges and produces a vocabulary of size $|V| = |C| + M$, where $|C|$ is the number of initial characters.

The intuition (an analogy that makes it click)

Think of your corpus as a long string of beads where each bead is a character and small common sequences of beads form patterns like "th" or "ing". BPE looks for the pair of adjacent beads that occurs most often and fuses them into a new bead. Repeat that a number of times and you will have new beads for common substrings. For new words, we then assemble beads from left to right using the learned fused beads, producing short tokens for common parts and longer sequences for rarer parts.

How it actually works (the real mechanics, with one concrete worked example)

Algorithm sketch:

1. Initialize the vocabulary to all characters appearing in the corpus plus an explicit end-of-word marker, for example underscore _.
2. Count all adjacent symbol pair frequencies across the corpus (including the end-of-word marker positions).
3. Find the most frequent pair and merge it into a new token. Replace all occurrences of that pair with the new token.
4. Repeat steps 2 and 3 for $M$ merges or until other stopping criteria.

A few formulas to keep handy. After $M$ merges the vocabulary size is:

where $|C|$ is number of initial distinct characters.

Worked example

Corpus (with counts):

• low appears 2 times
• lower appears 1 time
• newest appears 1 time

We mark ends with underscore so sequences are:

• l o w _ (2 times)
• l o w e r _
• n e w e s t _

Initial adjacent pair counts (summing occurrences):

Step 1: highest pair tie l o and o w with count 3. Suppose we merge l o -> lo.

New sequences after merge:

• lo w _ (2x)
• lo w e r _
• n e w e s t _

Recount pairs and pick the next highest frequency pair, for example o w is now part of lo w so the pair (lo,w) and (w,_) etc. We continue merging for $M$ steps. After 3 merges we might have tokens like: lo, w, er, newest as subwords depending on choices.

This example shows the greedy nature: early merges for high-frequency pairs produce tokens that shorten common words like low and lower while leaving rare words split into subwords.

Choosing vocabulary size and merges

Two practical knobs:

• Number of merges $M$. More merges increase vocabulary and create longer tokens for frequent substrings. Fewer merges keep tokens small and the model often needs more tokens per sentence.
• Which data you train on. Training on in-domain data makes merges reflect domain substrings.

Common rule of thumb: pick $M$ so that $|V|$ matches your target model embedding table size. If you want a vocabulary around 50k tokens and you have $|C|=100$ characters then set $M \approx 49900$ since

Comparison with other subword methods

Tradeoffs and failure modes

BPE strengths:

• Simple and fast to train and apply.
• Produces short tokens for frequent substrings reducing sequence lengths.

BPE weaknesses:

• Greedy merges can lock in suboptimal splits if early merges were unlucky.
• Not probabilistic; cannot revise earlier merge decisions easily.

Questions the interviewer might ask

Some follow-up questions you might get:

How does tokenization of unseen words work with BPE? You apply the learned merges greedily: start from characters and repeatedly apply merges in the order they were learned, or use a longest-match left-to-right strategy, producing subwords that were in the vocabulary. Unseen words break into known subwords or characters.

How do we decide the number of merges $M$? Match model capacity and practical limits. Choose $M$ so that $|V|$ fits embedding memory and gives acceptable average token length on validation text. Try several values and measure tokens-per-sentence and downstream performance.

What is the complexity of training BPE? A naive implementation recomputes pair counts each iteration, leading to roughly $O(N M)$ work for corpus size $N$ and $M$ merges. Optimized implementations update local counts and use priority queues to reduce overhead.

How does BPE compare to WordPiece and the Unigram model? BPE is greedy and deterministic. WordPiece is similar but optimizes likelihood heuristics. Unigram trains a probabilistic vocabulary then uses dynamic programming for segmentation. Each has different tradeoffs in tokenization consistency and runtime.

Can BPE produce ambiguous tokenizations? With a fixed merge order and longest-match strategy the tokenization is deterministic, so you do not get multiple segmentations. That determinism can be a pro or con depending on whether you wanted alternate splits.

Some things to note:

• The vocabulary size grows linearly with number of merges: $|V| = |C| + M$.
• Early merges strongly influence final tokens; training corpus choice matters.
• Use end-of-word marker to prevent merges across word boundaries when desired.

What the interviewer is really testing

They want to see you understand how subword tokenizers transform raw text into model tokens and the consequences of the greedy merge process. They also want to hear practical concerns: how $M$ affects model memory and sequence length, how tokenization behaves on new text, and failure modes for morphologically rich languages. Explaining a small worked example and the formula for vocabulary growth shows both algorithmic and practical grasp.