Foundations — Byte-Pair Encoding (BPE)

Before you can read the parent note on Byte-Pair Encoding (BPE), you need to be fluent in the handful of symbols and ideas it throws around. This page builds every one of them from nothing. Read top to bottom — each idea leans on the one above it.

1. What is a "corpus"?

The picture: imagine a jar full of words. Some words (like "the") appear thousands of times; others (like "widget") appear rarely.

Why the topic needs it: BPE cannot invent good subword chunks out of thin air. It learns which chunks are useful by looking at what actually appears — and how often — in the corpus. No corpus, no BPE.

2. Characters, words, and tokens

Look at the figure. The same word newest is shown chopped three different ways:

• char-level (7 tiny boxes) — many boxes, tiny vocabulary.
• word-level (1 big box) — few boxes, but a giant vocabulary to store every possible word.
• subword / BPE (new + est) — the middle ground.

Why the topic needs it: BPE lives entirely in the space between character and word. The whole point is choosing a token that is bigger than a character but not necessarily a full word.

3. The word boundary marker </w>

The picture: think of it as a full stop stuck to the tail of each word. low becomes the sequence l, o, w, </w>.

Why the topic needs it: several of the parent's learned merges — like ug</w> and bug</w> — only make sense because </w> exists as a mergeable symbol.

4. An "adjacent pair"

In the figure, slide a little window of width 2 across the word. Every position the window covers is one adjacent pair. That sliding window is literally what the algorithm does when it counts pairs.

Why the topic needs it: BPE's one and only move is "find the most frequent adjacent pair and glue it together". Everything hangs on this notion.

5. Frequency and word counts

The picture: imagine tally marks. Each occurrence of the word stamps its pairs that many times onto a scoreboard.

Why the topic needs it: "merge the most frequent pair" is a comparison of these tallies. Multiplying by word count is what makes rare words rare and common words common in the eyes of the algorithm.

6. Vocabulary and the symbol $V$

We write a growing vocabulary as $V_0,V_1,V_2,\dots$ — the subscript is just a step counter. $V_0$ is the starting set (all characters), and each merge adds one token:

$V_{i+1}=V_i\cup \{\text{merged\_pair}\}$

The picture: a jar of tokens that gets exactly one new marble dropped in per round.

Why the topic needs it: the algorithm stops when the jar reaches size $V$. That stopping condition is the whole reason BPE gives you a fixed, predictable vocabulary.

7. Merge rules and their order

The figure shows why order is sacred. Rule 2 es t → est needs the token es to already exist, and es only exists because rule 1 ran first. Apply them out of order and rule 2 finds nothing to bite on.

Why the topic needs it: at inference time (encoding a brand-new word) BPE does not re-count anything — it just replays the saved merge rules in order, like following a recipe step by step.

8. Sequence length $L$, corpus size $C$, and tokens-per-symbol $k$

These relate by one honest little formula:

$L_{\text{BPE}}\approx \frac{C}{k}$

The picture: cutting a rope of length $C$ into pieces of length $k$ gives $C/k$ pieces.

The ratio of how much shorter BPE is than plain characters is the compression ratio:

$R=\frac{L_{\text{char}}}{L_{\text{BPE}}}=\frac{C}{C/k}=k$

Why the topic needs it: this is the entire selling point of BPE — shorter sequences than character-level, without the exploding vocabulary of word-level.

9. How these foundations feed the topic

Read it top-down: text gives characters and words; adding the end-of-word marker and forming adjacent pairs lets you count frequencies; the most frequent pair gets merged; that grows the vocabulary and records a rule; and the tradeoff symbols explain why the resulting tokens are the right size. Together they are Byte-Pair Encoding (BPE).

10. Where this sits in the bigger map

• The problem BPE solves is set up in 4.2.01-Tokenization-Overview.
• Two close cousins tweak the merge criterion: 4.2.03-WordPiece-Tokenization (merges by likelihood, not raw frequency) and 4.2.04-SentencePiece (works on raw bytes, no pre-splitting on spaces).
• The tokens BPE produces become integer IDs that feed the 3.1.05-Embedding-Layer, which turns them into vectors for a model — see 4.3.01-Language-Model-Basics.
• The compression ratio $k$ directly affects speed at generation time: 6.2.02-Inference-Optimization.
• Prefer Hinglish? Read 4.2.02 Byte-Pair Encoding (BPE) (Hinglish).

Equipment checklist

Cover the right side and see if you can answer each before revealing.