# Byte-Pair Encoding

Building a vocabulary by repeatedly merging the most frequent adjacent pair, yielding subword units that cover any input without unknown tokens.

**Rests on:** Tokenization

**Leads to:** Cross-Lingual Transfer

*LLMs and Generative AI · Large Language Models*


## Why learn this

Byte-Pair Encoding is the first piece of the tokenisation pipeline that every large language model — including ChatGPT-style models and small on-device ones — uses to turn text into numbers the model can read. Without it, you cannot understand why your prompt costs a certain number of tokens, why some languages are cheaper than others, or why the model struggles with arithmetic. Master this, and you unlock your library's notes on Tokenization, Token IDs and Special Tokens, the Context Window, and ultimately the entire Large Language Models topic. It is the quiet foundation under everything else.


## The intuition

Think of the English language as a set of building blocks. You could use single letters — 'c', 'a', 't' — and spell every word as a sequence of letters. That works, but it is wasteful: the word 'the' would need three blocks every single time you write it. At the other extreme, you could use whole words as blocks — 'the', 'cat', 'sitting' — but then any word you have never seen before, like a new name or a typo, has no block and you are stuck. Byte-Pair Encoding finds a middle ground. It starts with single letters (technically bytes, but think letters for now) and then looks at your entire training corpus — all the text the model will learn from — and finds which two blocks appear together most often. It merges those two into one new block. Then it repeats: find the most frequent adjacent pair among the current set of blocks, merge them, repeat. After many rounds, you have a vocabulary of blocks: some are whole frequent words like 'the', some are common parts like 'ing', and some are single letters. When you later see a new word like 'unalone', you can break it into pieces you already have: 'un', 'al', 'one' — or if nothing matches, down to single letters. So no word is ever unknown: the worst case is you spell it letter by letter. This is exactly the intuition from your library: 'Frequent words become single tokens; rare ones decompose into pieces.' The magic is that the merges are learned from data, not chosen by a linguist, and after training they are frozen — the model never changes its vocabulary again.


## An analogy

Imagine you are a librarian who has to file every sentence as a sequence of cards. Initially, each card holds one letter. You notice the cards 't' and 'h' appear together very often, so you create a new card 'th' and replace every adjacent 't','h' pair with this single card. That saves space and speeds up your filing. Then you notice 'th' and 'e' together are common, so you make a 'the' card. Over time, you build a drawer of cards: some are whole words like 'the', some are parts like 'ing', and some are single letters. When a new document arrives with a word you've never filed before, like 'xylophone', you can always spell it with single-letter cards — 'x','y','l','o','p','h','o','n','e' — so you are never stuck. The analogy stops working at one point: in reality, the merges are decided purely by frequency in a large corpus, not by any sense of meaning. The librarian might merge 'q' and 'u' because they are frequent, but she might also merge 'e' and 'r' if they happen to appear together often, even though 'er' is a meaningful suffix. There is no grammar in the process — just statistics. Also, the librarian would never merge letters across word boundaries (like 'e' and space) because spaces are handled separately in modern tokenisers, but the principle is the same.


## Definition

Byte-Pair Encoding (BPE) is an algorithm that builds a token vocabulary by starting with individual bytes and repeatedly merging the most frequently occurring adjacent pair in a training corpus, until the vocabulary reaches a target size.


## How it connects

This concept connects directly to your library's notes on Tokenization (the process of splitting text into units), Token IDs and Special Tokens (each BPE token gets an integer ID), and the Context Window (the number of tokens limits the window size). It is the first step in the Large Language Models pipeline, before embeddings and attention. You have just learned this from scratch, so this fills the gap between raw text and the model's input.


## The mathematics

Byte-Pair Encoding is a method for shrinking a list of characters into a smaller set of symbols, called tokens. It does not use algebra, calculus, or complex formulas. It uses only two operations: counting and replacing.

The goal is to create a vocabulary of a specific size, let us call this target size N. For example, if we want a vocabulary of 100 symbols, we start with many more (like all possible byte values) and reduce that number until we have exactly 100.

Here is the step-by-step process:

1. Start with your text as a sequence of individual characters. Each character is its own symbol. Let V be the set of all current symbols. Initially, V contains every unique character in your text.

2. Count every pair of adjacent symbols in the entire text. "Adjacent" means they sit next to each other with nothing in between. For example, in the word 'cat', the pairs are ('c','a') and ('a','t').

3. Find the pair that appears most often. Let us call this pair (x, y). If there is a tie, pick any one of the tied pairs.

4. Create a new symbol by joining x and y together. Call this new symbol xy. Add xy to your set V.

5. Replace every occurrence of the sequence x followed by y in the text with the single new symbol xy. This shortens the text.

6. Check the size of V. If V has fewer than N symbols, go back to step 2 and repeat the counting and merging on the shortened text. If V has reached or exceeded N, stop.

The mathematics here is purely arithmetic: addition (counting occurrences) and substitution (replacing pairs). There are no equations to solve for unknowns. The only rule is that you always merge the most frequent adjacent pair available at that moment.

Why does this work? By merging the most common pairs, we capture the most frequent structures in the language first. Rare characters remain as single symbols, while common combinations become single tokens. This allows the model to process text more efficiently because it handles frequent chunks as single units.


## A worked example

Let us walk through a small example with real numbers.

Suppose our target vocabulary size N is 6. We start with the single word: 'aaabdaaabac'.

Initial Vocabulary V: {a, b, c, d}. The size of V is 4. Since 4 < 6, we must merge.

Step 1: Count adjacent pairs in 'aaabdaaabac'.
Write the sequence of symbols:
a, a, a, b, d, a, a, a, b, a, c

List every adjacent pair (the first symbol followed by the second):
1. (a, a)
2. (a, a)
3. (a, b)
4. (b, d)
5. (d, a)
6. (a, a)
7. (a, a)
8. (a, b)
9. (b, a)
10. (a, c)

Now count how many times each unique pair appears:
- The pair (a, a) appears 4 times.
- The pair (a, b) appears 2 times.
- The pair (b, d) appears 1 time.
- The pair (d, a) appears 1 time.
- The pair (b, a) appears 1 time.
- The pair (a, c) appears 1 time.

The most frequent pair is (a, a) with a count of 4.

Step 2: Merge the pair (a, a).
Create a new symbol. Let us call it 'aa'.
Add 'aa' to V. Now V = {a, b, c, d, aa}. The size of V is 5. Since 5 < 6, we must merge again.

Replace every occurrence of 'a' followed by 'a' with the single symbol 'aa' in the original sequence.
Original: a, a, a, b, d, a, a, a, b, a, c
First 'a','a' becomes 'aa'. The remaining 'a' is just 'a'.
Sequence becomes: aa, a, b, d, aa, a, b, a, c

Step 3: Count adjacent pairs in the new sequence.
Write the sequence of symbols:
aa, a, b, d, aa, a, b, a, c

List every adjacent pair:
1. (aa, a)
2. (a, b)
3. (b, d)
4. (d, aa)
5. (aa, a)
6. (a, b)
7. (b, a)
8. (a, c)

Count how many times each unique pair appears:
- The pair (aa, a) appears 2 times.
- The pair (a, b) appears 2 times.
- The pair (b, d) appears 1 time.
- The pair (d, aa) appears 1 time.
- The pair (b, a) appears 1 time.
- The pair (a, c) appears 1 time.

There is a tie between (aa, a) and (a, b), both with a count of 2. We must pick one. Let us arbitrarily choose (aa, a).

Step 4: Merge the pair (aa, a).
Create a new symbol by joining 'aa' and 'a'. Call it 'aaa'.
Add 'aaa' to V. Now V = {a, b, c, d, aa, aaa}. The size of V is 6.

Check the target: Is the size of V equal to N? Yes, 6 = 6. We stop.

Final Vocabulary: {a, b, c, d, aa, aaa}
Final Encoded Sequence: aaa, b, d, aaa, b, a, c

Notice that the original word had 11 characters. The encoded sequence has 7 symbols. The vocabulary grew from 4 to 6 symbols. Each merge reduced the length of the text by one symbol.


## From scratch, in Python

```python
# Step 0: Our training corpus as a list of characters (bytes simplified)
corpus = "low lower lowest newest"
# We'll use a list of single-character strings for simplicity
# In real BPE, we'd use bytes, but this shows the idea.

# Step 1: Define a function to count adjacent pairs
def get_pair_counts(tokens):
    # tokens is a list of strings (each a symbol)
    pairs = {}
    for i in range(len(tokens) - 1):
        pair = (tokens[i], tokens[i+1])
        # If pair already in dictionary, add 1; else set to 1
        if pair in pairs:
            pairs[pair] += 1
        else:
            pairs[pair] = 1
    return pairs

# Step 2: Function to merge the most frequent pair
def merge_pair(tokens, pair):
    # pair is a tuple like ('l', 'o')
    new_tokens = []
    i = 0
    while i < len(tokens):
        # If we are at the last token, just add it
        if i == len(tokens) - 1:
            new_tokens.append(tokens[i])
            i += 1
        # Check if the current token and the next form the pair
        elif (tokens[i], tokens[i+1]) == pair:
            # Merge them into a single token (concatenate the strings)
            new_tokens.append(tokens[i] + tokens[i+1])
            i += 2  # skip the next token
        else:
            new_tokens.append(tokens[i])
            i += 1
    return new_tokens

# Step 3: Run the algorithm for a fixed number of merges (say 3)
tokens = list(corpus)  # each character is a token initially
print("Initial tokens:", tokens)
for num_merges in range(3):
    pair_counts = get_pair_counts(tokens)
    # Find the pair with the highest count
    # If no pairs, break
    if not pair_counts:
        break
    best_pair = max(pair_counts, key=pair_counts.get)
    print(f"Merge {num_merges+1}: most frequent pair is {best_pair} with count {pair_counts[best_pair]}")
    tokens = merge_pair(tokens, best_pair)
    print("After merge:", tokens)

print("Final vocabulary:", set(tokens))
```


## The same thing, with a framework

```python
In practice, you would not write BPE from scratch. Libraries like Hugging Face's tokenizers implement it. The key function is `tokenizers.BertWordPieceTokenizer` or `tokenizers.ByteLevelBPETokenizer` (for GPT-style models). Here is an example use:

from tokenizers import ByteLevelBPETokenizer

# Initialize a BPE tokenizer with a target vocabulary size
tokenizer = ByteLevelBPETokenizer()
# Train on a text file (or list of texts)
tokenizer.train(["corpus.txt"], vocab_size=1000, min_frequency=2)
# Now encode any text
tokens = tokenizer.encode("Hello, world!")
print(tokens.ids)  # integer IDs for each token
print(tokens.tokens)  # the subword pieces

Under the hood, this does exactly what you wrote above: counts pairs, merges, repeats, until the vocab size is reached. The library just does it efficiently in Rust.
```


## What the code does

The code first creates a corpus as a string and converts it to a list of characters using `list(corpus)`. This is a Python list — an ordered collection that can be changed. We then define two functions. A function is a reusable block of code that takes an input and returns an output. `get_pair_counts` takes a list of tokens and returns a dictionary where each key is a pair of adjacent tokens (a tuple) and the value is how many times that pair appears. It loops over the list with `for i in range(len(tokens) - 1)`, which goes through each index except the last, and checks the pair at positions i and i+1. The dictionary lookup `if pair in pairs` is the Python way to check if a key exists; if it does, we increment the count, else we set it to 1. The `merge_pair` function takes the list of tokens and a pair to merge. It iterates with a while loop, building a new list. If the current token and the next match the pair, it concatenates them into a single string (like 'l' + 'o' -> 'lo') and skips ahead by two indices; otherwise it copies the current token and moves on. The main loop runs three merges: it counts pairs, finds the most frequent using `max` with a key function, prints the pair, and then merges. At the end, `set(tokens)` gives the unique tokens in the vocabulary — a set is a Python collection that stores each item once, without order. Running this on the sample corpus will show how 'lo' or 'ow' become merged. The framework version with `ByteLevelBPETokenizer` does the same thing but handles bytes, spaces, and efficient training on large corpora.


## Common misconceptions

**BPE splits words into meaningful chunks** — The subwords that BPE creates always correspond to real prefixes, suffixes, or meaningful parts of words.

BPE only looks at frequency. It will happily merge 'e' and 'r' into 'er' because that is common, but it might also merge 'q' and 'u' or even pieces like 'a' and 'b' if they happen to co-occur often in the training data. There is no linguistic or semantic analysis at all. In fact: BPE is purely statistical. The subwords are whatever the data suggests, not what a linguist would choose.

**BPE can encounter unknown words** — If a word is not in the vocabulary, the tokeniser raises an error or outputs a special 'unknown' token.

Because BPE falls back all the way to individual bytes (or characters), every possible string can be represented. The algorithm guarantees coverage because any sequence of bytes is a sequence of tokens — you just might use many pieces. In fact: BPE has no out-of-vocabulary problem by design. Any new word is decomposed into subword pieces, down to single bytes if needed.

**The vocabulary is fixed forever after training** — The model can learn new tokens during fine-tuning if it encounters new words.

The merge rules are learned during pretraining and then frozen. The model's vocabulary and the mapping from tokens to IDs are fixed. When fine-tuning, you either use the same tokeniser or explicitly extend the vocabulary (which is rare and often requires re-embedding). In fact: The BPE vocabulary is set during pretraining and does not change during fine-tuning or inference. New words are handled by decomposition, not by adding tokens.

**BPE is the same as word tokenisation** — BPE just splits on spaces and punctuation, like a simple word tokeniser.

A word tokeniser splits into whole words, so any unseen word becomes an unknown token. BPE starts with bytes and merges based on frequency, so it can split a word into multiple pieces and also merge across what a human would consider word boundaries (though spaces are usually handled as tokens). In fact: BPE produces subword units that are a middle ground between characters and words. It can split a single word into several tokens and also combine common words into single tokens.

**More merges always make the model better** — Increasing the vocabulary size (more merges) always improves model performance.

There is a sweet spot. If the vocabulary is too large, tokens become too specific, and the model may not generalise to new words. If it is too small, too many pieces per word make sequences long and training slower. The optimal size depends on the training data and the model's compute budget. In fact: The vocabulary size is a hyperparameter that needs to be tuned. Larger is not always better; it is a trade-off between granularity and model capacity.


## In short

Byte-Pair Encoding turns raw text into a fixed vocabulary of subword tokens by repeatedly merging the most frequent adjacent pair. It is data-driven, guarantees no out-of-vocabulary tokens, and is the foundation of every modern LLM's input pipeline. The vocabulary and merge rules are learned once and then frozen. The token vocabulary affects cost, multilingual quality, and arithmetic ability, making it a secretly important design choice.


## Where this is used

Byte-Pair Encoding is the workhorse tokenisation algorithm behind nearly every modern LLM, including GPT-4, Llama, and Mistral. Here is how it shows up in each area:

**Large language models.** When you send a prompt to an LLM, the raw text is first broken into BPE tokens. Each token is mapped to an integer ID, and that sequence of IDs is what the transformer actually reads. The vocabulary size — typically 32,000 to 100,000 — is a hyperparameter set during training. The merge rules are learned once on the training corpus and then frozen; the model never sees raw text again. This means the model's knowledge of spelling is entirely based on the subword units. For example, the word 'unbelievable' might be split into 'un', 'belie', 'vable' if those subwords are frequent. The cost of your prompt is measured in tokens, and BPE directly determines how many tokens a given string takes. English tends to be about 1 token per 4 characters, but other languages can be much more expensive because their characters are less frequent in the training data. This is why multilingual models often have larger vocabularies. Tokens also affect arithmetic: a number like '1234567' might be split into '123', '456', '7' or similar, and the model has to learn to add these pieces, which is why LLMs are often bad at arithmetic.

**Small models on devices.** TinyML and on-device models use the same BPE algorithm but with smaller vocabularies (e.g., 8,000–16,000 tokens) to keep memory down. The tokeniser runs on the device, converting speech-to-text output or typed text into token IDs before passing them to the small model. The trade-off is that a smaller vocabulary means more rare words are split into smaller pieces, which can degrade quality but saves RAM. For example, a keyword spotter like 'Hey Siri' might use a tiny BPE vocabulary that includes whole common phrases.

**Retrieval-augmented generation (RAG).** In RAG, you embed documents and query text into vectors for similarity search. The embedding model first tokenises the text using BPE. The choice of tokeniser affects the quality of embeddings: if a rare word is split into pieces that each have no semantic meaning, the embedding may be poor. Many embedding models share the tokeniser of the base LLM, so consistency matters. When you build a RAG system, you must ensure the same tokeniser is used for both indexing and querying, otherwise the embeddings will not align.

**Agentic systems.** Agents that plan and call tools often need to parse structured outputs (JSON, code) and handle long context. BPE determines the token count, which directly affects the context window budget. When an agent loops and accumulates tool results, each turn adds tokens; BPE efficiency is crucial to avoid blowing the context limit. Also, agents that write code need a tokeniser that treats spaces and punctuation consistently; some tokenisers create separate tokens for whitespace, which can affect code generation quality.

**Everyday applied ML.** Beyond LLMs, BPE is used in any sequence-to-sequence model that deals with text, including machine translation, text summarisation, and speech recognition (where the text output is tokenised). It is also used in some non-neural NLP pipelines for feature extraction. A developer working with Hugging Face's `transformers` library simply loads a pretrained tokeniser and calls `tokenizer(text)`, getting a dictionary with `input_ids` and `attention_mask`. The hard part is when they want to add new tokens or fine-tune on domain-specific jargon; then they must decide whether to extend the vocabulary or rely on the existing subwords. Getting this wrong can lead to out-of-vocabulary tokens or poor performance on rare terms.

**What breaks when done badly.** If you train BPE on a corpus that is not representative of your deployment data (e.g., only English when you serve Hindi), the tokeniser will split Hindi words into many pieces, inflating token counts and cost, and degrading quality. If you set the vocabulary too small, the model has to represent everything with few subwords, harming rare words. If you set it too large, training is slower and the model may overfit to rare tokens. Also, if you do not apply the same pre-tokenisation rules (like separating punctuation), the merges can produce units that cross word boundaries, confusing the model. A well-known bug is when a tokeniser splits numbers inconsistently, causing arithmetic failures.


---

Read this on the web: https://basavapurushottam.com/learn-ai/byte-pair-encoding
