What is byte pair encoding? How BPE tokenization works

In this article

1. Before you start
2. Why interviewers ask this
3. Byte pair encoding 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

Why interviewers ask this

Tokenization sits under every other number in a language-model system, so a candidate who cannot explain it cannot explain cost, latency or odd failures. Questions arrive in several forms: explain tokenization and why it drives cost, explain the trade-offs of a large vocabulary, or implement BPE on a whiteboard. A weak answer says "it splits text into words". A strong answer describes the merge loop, says what the stopping point costs in memory and sequence length, and knows why the same model counts letters and digits badly. The three-part answer to practise is: the loop, the cost of the size, the failure it causes. This page builds each part from zero.

Byte pair encoding from first principles

Merge rule

A merge rule is a saved instruction of the form "wherever u is followed by g, write the single symbol ug" that BPE learns during training and replays in order when encoding.

Byte-level BPE

Byte-level BPE is BPE whose starting symbols are the 256 possible byte values instead of characters, so any text, in any language, can be encoded without an unknown token.

In plain words

Think of a shorthand writer. They notice that "th", "the" and "ing" keep appearing. So they invent one symbol for each. After enough symbols, common words cost one stroke. Rare words still cost several. The analogy breaks in one place. A shorthand writer picks symbols by taste. BPE picks them by counting and knows nothing of meaning. So a token can be a whole word or a meaningless fragment.

In one precise sentence: BPE starts from single symbols and repeatedly merges the most frequent adjacent pair into a new symbol, saving each merge as a rule, until the vocabulary reaches a chosen size. The idea began as a text-compression method. Sennrich, Haddow and Birch (2016) adapted it to split words into subword units for neural translation. The Hugging Face course tells the same history.

Step 1: Split every word into characters

Training starts with a corpus and a count of how often each word occurs. Real tokenizers first apply pre-tokenization, a fixed rule that cuts text into chunks such as words, spaces and punctuation; BPE never merges across two chunks. Each word is cut into single characters, and the set of characters seen becomes the base vocabulary. The Hugging Face course uses five words with counts: "hug" 10, "pug" 5, "pun" 12, "bun" 4 and "hugs" 5 (an illustrative corpus). The base vocabulary is the seven characters b, g, h, n, p, s and u.

At this point no word is a token yet; each is a row of characters, weighted by how often the word appears. The weights matter: a pair inside a common word counts for more than a pair inside a rare one.

1 · Split to characters2 · Count pairs3 · Merge the top pair4 · Repeat to a size5 · Encode new textReplay

Step-by-step description

1. Each word becomes single characters; seven base symbols.
2. Add each word's frequency to every adjacent pair it contains.
3. u + g appears 20 times, so it becomes the token ug.
4. Stop when the vocabulary reaches the size you chose.
5. Replay the saved rules in order: bug becomes b, ug.

• The toy corpus starts with a base vocabulary of seven characters.
• The pair u, g is counted 20 times in the toy corpus and is merged first.
• Each merge adds exactly one entry to the vocabulary and one rule to the saved list.
• Encoding replays the saved merge rules in the order they were learned.

Step 2: Count every adjacent pair

Walk along each word and count each neighbouring pair, adding the word's frequency each time. In the toy corpus the pair "u, g" appears in "hug", "pug" and "hugs", so its count is 10 + 5 + 5 = 20. The pair "p, u" appears in "pug" and "pun" for 17, and "u, n" appears in "pun" and "bun" for 16.¹

The output of this step is a table of pairs and counts. Nothing has changed in the corpus yet. The table is the evidence the next step uses, and it must be rebuilt after every merge, because a merge removes some pairs and creates new ones. Production implementations update the counts incrementally instead of recounting the whole corpus, which is an engineering shortcut and does not change the result.

Step 3: Merge the most frequent pair and save the rule

Pick the pair with the highest count, here "u, g" at 20, and replace it everywhere with the new symbol "ug". Add "ug" to the vocabulary and write the rule "u + g → ug" at the end of the merge list. The vocabulary grows by exactly one entry per merge.

The order of the list is part of the tokenizer: two lists with the same rules in a different order can tokenize the same word differently. Later rules may use symbols that earlier rules created: after "ug" exists, the pair "h, ug" becomes a candidate and wins the third merge with 15 occurrences, producing "hug".¹

Step 4: Stop at the vocabulary size you chose

Repeat steps 2 and 3 until the vocabulary reaches the size you decided on. Real systems stop at tens of thousands to a few hundred thousand entries: Meta's Llama 3 post states a 128K vocabulary and "up to 15% fewer tokens" than Llama 2, and the tiktoken encodings have 100,277 and 200,019 entries as counted in our script.¹

The stopping point is a design choice with a bill attached. Every vocabulary entry owns one row in the input embedding table and, in most models, one row in the output layer. With an illustrative embedding width of 4,096, a 32,000-entry vocabulary is 131 million numbers per table and a 200,000-entry vocabulary is 819 million.¹ A larger vocabulary shortens text, which saves attention compute and key-value (KV) cache memory, and costs table memory; it also leaves rare tokens with a thinner training signal.

Step 5: Encode new text by replaying the rules

To tokenize new text, split it into base symbols and apply the merge rules in the order they were learned. The unseen word "bug" becomes "b, ug", because the rule "u + g → ug" fires and nothing merges "b" with it. "pugs" becomes "pug, s".¹

A word with no matching rules falls back to its base symbols. In a character-level vocabulary that is where trouble starts: "zip" contains characters, z, that never appeared in training, so an out-of-vocabulary (OOV) symbol would be needed. Byte-level BPE removes the problem by starting from bytes; the tiktoken README states that its BPE is reversible and lossless and works on arbitrary text, and the SentencePiece paper trains directly on raw sentences so the method does not depend on a language-specific word splitter.

Worked example

The toy corpus produces these merges. Each row is computed by the script, not typed by hand.¹

Text description of the diagram

• On the toy corpus the chosen pair counts are 20, 16, 15, 12, 5 and 5 for merges one to six.
• The vocabulary grows from 7 to 13 entries over six merges.

The first three rows match the Hugging Face course example exactly. Merges 4 to 6 continue the same procedure. Merges 5 and 6 tie at a count of 5, and the script breaks ties by sorted order; real implementations choose a tie-break rule too, and it changes the vocabulary slightly. After six merges "hug", "pug", "pun" and "hugs" are single tokens and "bun" is "b, un".

The whole training loop is short:

from collections import Counter
words = {w: list(w) for w in corpus}          # word -> symbols
for _ in range(num_merges):
    pairs = Counter()
    for w, f in corpus.items():
        for a, b in zip(words[w], words[w][1:]):
            pairs[(a, b)] += f                # weight by word frequency
    best = max(sorted(pairs), key=pairs.get)  # most frequent pair
    merge_everywhere(words, best)             # replace (a, b) with "ab"

With real tokenizers the same arithmetic shows up in sentences. The sentence "Tokenization turns text into integers." is 38 bytes and encodes to 7 tokens in both the cl100k_base and o200k_base encodings, a ratio of about 5 bytes per token, and it decodes back to the exact input.¹ That ratio is for one English sentence; the tiktoken README gives roughly 4 bytes per token as an average.

Trade-offs and edge cases

A vocabulary size has no neutral setting. The table summarises the pressure on both sides.

Text description of the diagram

• A larger vocabulary gives fewer tokens per text, which shortens sequences.
• The embedding table has one row for every vocabulary entry, so it grows with the vocabulary.
• A large vocabulary leaves rare tokens with a thinner training signal.

Numbers fragment, and the pre-tokenizer decides how. In the older r50k_base encoding the digits "12345678" are one chunk, and BPE splits them by frequency into "123", "45" and "678". The cl100k_base and o200k_base encodings add a pre-tokenization rule that cuts every run of digits into groups of at most three before BPE runs, so the same digits always become "123", "456" and "78".¹ Either way the model never sees the number as a unit, and arithmetic on long numbers is harder.

The tokenizer is welded to the model. The embedding rows are trained against the exact ids, so swapping the tokenizer after pretraining breaks the model; a new tokenizer means new embeddings and retraining.

Other languages pay more. A vocabulary learned mostly from English splits other scripts into more pieces, which raises their cost and lowers their effective context window. Reported practice differs on how to fix it: widen the vocabulary, as the Llama 3 paper (July 2024) did by adding 28K tokens to 100K tiktoken tokens to better support non-English languages, or train the tokenizer on a more balanced corpus.

Neighbours of BPE. WordPiece chooses merges by a likelihood score instead of raw counts, and SentencePiece is a library that applies BPE or a unigram model to raw text.

How to answer it in an interview

The spoken structure is: the loop in one sentence, the cost of the stopping point, then one failure it causes.

Common mistakes

"BPE splits text into words." (wrong) Words are only the pre-tokenization step; BPE learns subword pieces from counts, and a common word may be one token while a rare one is several. (right) "BPE learns subword units by merging frequent pairs."

"A bigger vocabulary is always better." (wrong) It shortens sequences, but the embedding and output tables grow with the entry count and rare tokens see few examples. (right) "It trades sequence length against table size and training signal."

"BPE loses information." (wrong) Byte-level BPE is reversible: the round trip in our script returned the exact sentence. (right) "Byte-level BPE is lossless; a character-level vocabulary with an unknown token is not, and in both the model loses the view of letters inside a token."

"You can swap the tokenizer later." (wrong) The embeddings are tied to the ids. (right) "A new tokenizer needs new embeddings and retraining."

Follow-up questions

Is byte pair encoding lossy or lossless?

Byte-level BPE is lossless: the tiktoken README calls it reversible and lossless, and our run decoded 7 tokens back to the original 38-byte sentence exactly.¹ A model may still lose information in a different sense, because it cannot see the letters inside a token.

Who invented byte pair encoding?

BPE began as a text-compression algorithm, as the Hugging Face course notes, and was adapted for subword segmentation in neural machine translation by Sennrich, Haddow and Birch, whose paper first appeared in August 2015 and was revised in June 2016.

Why do LLMs struggle with counting letters?

The model sees token ids, not letters. A word such as "tokenization" arrives as a few multi-letter chunks, so the letter count is not directly visible and has to be inferred from training.

What happens with a 1M vocabulary?

Sequences get shorter, but at width 4,096 the table alone would hold about 4.1 billion numbers per copy, and most tokens would be rare and poorly trained.¹ Diminishing returns arrive well before that size.

How would you tokenize a new language?

Train a byte-level or SentencePiece-style tokenizer on a balanced sample of that language, and check bytes per token against the existing tokenizer. For a pretrained model, plan the embeddings: replacing its tokenizer invalidates every id, while extending it keeps the old ids but adds rows that continued pretraining must train. Read the transformer hub and the large language model (LLM) inference hub for what token counts do to cost, and see graphics processing unit (GPU) fundamentals for why table size matters.

Sources

1. Neural Machine Translation of Rare Words with Subword Units — arXiv (Sennrich, Haddow, Birch), v5, 10 Jun 2016
2. Byte-Pair Encoding tokenization (LLM Course, chapter 6) — Hugging Face, 24 Oct 2026
3. tiktoken: a fast BPE tokeniser for use with OpenAI's models — OpenAI (GitHub), 24 Oct 2026
4. SentencePiece: A simple and language independent subword tokenizer and detokenizer — arXiv (Kudo, Richardson), 19 Aug 2018
5. The Llama 3 Herd of Models — arXiv (Llama Team, AI @ Meta), v3, 31 Jul 2024
6. Introducing Meta Llama 3 — Meta AI, 18 Apr 2024