Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 53 Β· Tokens and Embeddings

Byte-Pair Encoding from Scratch

Build byte-pair encoding step by step: count pairs, merge the most frequent, train a tiny vocabulary, then encode and decode text, including byte-level BPE.

Byte-pair encoding, or BPE, is the algorithm behind the vocabularies of most large language models. The idea is simple enough to write in about twenty lines of Python: start with single characters, then repeatedly glue together the pair of neighbours that occurs most often. Each glue operation is called a merge, and after enough merges, common words become single tokens while rare words stay split into pieces.

This lesson assumes you know why models use subword tokens; if not, read Tokens and Tokenization first. You will train a tiny vocabulary, watch the merges happen, and then use them to encode and decode new text.

BPE in four steps

Start Every word is a list of characters.
Count Find the most frequent neighbouring pair.
Merge Replace that pair with one new symbol.
Repeat Stop at the vocabulary size you want.

The ordered list of merges is the tokenizer.

1 / 2

Counting pairs

Take a tiny corpus. We first count how often each word appears, and write each word as a tuple of characters plus an end-of-word marker _. The marker lets the tokenizer tell the end of low from the start of lower.

Then we count every adjacent pair of symbols, weighted by word frequency.

Python Count adjacent pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two pairs tie for first place: l+o and o+w, each with 7 occurrences (5 from low plus 2 from lower). One of them becomes the first merge.

One merge, then many

A merge walks through every word and replaces each occurrence of the chosen pair with the joined symbol. Doing this repeatedly is the whole training loop. We record each merge in order, because encoding must replay them in the same order.

Python Train a tiny BPE vocabulary

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After ten merges, frequent words such as low_ and newest_ have become single symbols, while widest_ is still partly split, because it is rarer. The tie-breaking rule (largest pair wins) is arbitrary but makes the result deterministic. Real implementations pick any fixed rule.

The vocabulary is the starting characters plus one new symbol per merge. Training for 30,000 merges on a big text sample gives a vocabulary of roughly 30,000 tokens plus the base alphabet.

Encoding new text

To encode a new word, split it into characters plus _, then apply the learned merges in the order they were learned. Merge number 1 is tried first, then number 2, and so on. This means the tokenizer is fully deterministic: the same text always gives the same tokens.

Unseen words work too. lowest was never in the corpus, but the merges still apply to its parts, so it becomes low and est_, two familiar tokens instead of an unknown one.

Python Encode and decode with learned merges

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every input round-trips through decode. The made-up word xyz simply stays as single characters, which is the safety net: no input can ever fail to encode.

Byte-level BPE

The version above starts from characters, so a character it has never seen (an emoji, a rare script) would have no token. Byte-level BPE, used by many production tokenizers, starts from the 256 possible bytes of UTF-8 instead. Any text in any language is a sequence of bytes, so the base alphabet is exactly 256 symbols and nothing can be unknown.

Common characters then merge into multi-byte tokens during training, while a rare emoji might stay as three or four separate byte tokens. You can see the byte view directly:

Python Text is a sequence of bytes

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Plain English letters use one byte each, while accented letters take two, many Asian characters three, and emoji four. A byte-level tokenizer trained mostly on English will therefore need more tokens for other scripts, which is the cost effect described in Counting Tokens and Estimating Cost.

Production tokenizers add a few more ideas on top of this core: a pre-tokenization step (often a regular expression) that splits text into word-like chunks before merging so that merges never cross, say, a word and the punctuation next to it; special tokens added by hand; and fast implementations that use a rank table instead of repeated scanning.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is the core operation repeated in BPE training?

    BPE counts neighbouring pairs and glues the most common one together, then repeats.
  2. 2. Why must encoding replay the merges in the order they were learned?

    Earlier merges are more frequent patterns. Applying them in the same order guarantees the same tokens every time.
  3. 3. What advantage does byte-level BPE have over character-level BPE?

    Any text is a byte sequence, so there are no unknown characters, even for emoji or rare scripts.
  4. 4. What happens to a word the tokenizer never saw during training?

    Merges only apply where the pieces match, so unseen words fall back to smaller known symbols.

Summary

  • BPE starts from characters (or bytes) and repeatedly merges the most frequent neighbouring pair.
  • The ordered merge list is the tokenizer; vocabulary size is the base alphabet plus the number of merges.
  • Encoding replays the merges in order, so it is deterministic and handles unseen words.
  • Byte-level BPE starts from 256 bytes, so no text is ever unknown, though rare scripts cost more tokens.
  • Real tokenizers add pre-tokenization and special tokens on top of this core.

Next: turn these token counts into money and budgets in Counting Tokens and Estimating Cost.