Byte Pair Encoding (BPE)

In previous lessons, we used entire words as tokens. While simple, this approach has two massive flaws:

1. Vocabulary Explosion: Every variation of a word (like hugging, hugged, hugs) needs its own entry.
2. OOV Problem: If the model sees a word it hasn't seen in training, it fails completely.

Byte Pair Encoding (BPE) is the solution. It works by looking for the most frequent character pairs and merging them into new tokens. Over time, it builds a vocabulary of characters, subwords, and full words.

Adapted from A deep understanding of AI language model mechanisms — https://udemy.com/course/dullms_x

1. Initializing the Vocabulary

BPE starts at the character level. We begin by breaking our text into individual characters.

# Example text with lots of repetitions
text = 'like liker love lovely hug hugs hugging hearts'

# Initial vocab: unique characters
chars = sorted(list(set(text)))
vocab = { char: i for i, char in enumerate(chars) }

# Text as a list of tokens
origtext = list(text)

print(f"Initial Vocabulary: {vocab}")
print(f"Tokens: {origtext[:10]}...")

Initial Vocabulary: {' ': 0, 'a': 1, 'e': 2, 'g': 3, 'h': 4, 'i': 5, 'k': 6, 'l': 7, 'n': 8, 'o': 9, 'r': 10, 's': 11, 't': 12, 'u': 13, 'v': 14, 'y': 15}
Tokens: ['l', 'i', 'k', 'e', ' ', 'l', 'i', 'k', 'e', 'r']...

2. Finding Frequent Pairs

The "magic" of BPE is identifying which pair of tokens appears most often together.

import numpy as np

def get_pair_stats(token_list):
  pairs = {}
  for i in range(len(token_list)-1):
    pair = token_list[i] + token_list[i+1]
    pairs[pair] = pairs.get(pair, 0) + 1
  return pairs

stats = get_pair_stats(origtext)
most_freq = max(stats, key=stats.get)

print(f"Frequent Pairs: {dict(list(stats.items())[:5])}")
print(f"Most Frequent: '{most_freq}' ({stats[most_freq]} times)")

Frequent Pairs: {'li': 2, 'ik': 2, 'ke': 2, 'e ': 2, ' l': 3}
Most Frequent: ' h' (4 times)

3. Merging Tokens

Once we find the most frequent pair (in this case, ' h'), we merge them. This creates a new token in our vocabulary and replaces all occurrences in the text.

def merge_tokens(prev_text, pair_to_merge):
  new_text = []
  i = 0
  while i < len(prev_text):
    # Check if we have a match
    if i < len(prev_text)-1 and (prev_text[i] + prev_text[i+1]) == pair_to_merge:
      new_text.append(pair_to_merge)
      i += 2
    else:
      new_text.append(prev_text[i])
      i += 1
  return new_text

# Update vocabulary
vocab[most_freq] = max(vocab.values()) + 1
updated_text = merge_tokens(origtext, most_freq)

print(f"Original length: {len(origtext)}")
print(f"New length:      {len(updated_text)}")
print(f"New tokens:      {updated_text[:15]}...")

Original length: 46
New length:      42
New tokens:      ['l', 'i', 'k', 'e', ' ', 'l', 'i', 'k', 'e', 'r', ' ', 'l', 'o', 'v', 'e']...

Why this is powerful

By merging ' h', we've started to group characters that often go together. If we keep doing this, we might eventually merge 'h', 'u', and 'g' into one token: 'hug'.

This allows the model to:

• Use one token for common words (efficient).
• Fall back to individual characters for rare words (robust).

In the next lesson, we'll build a loop to run this process automatically until we reach a target vocabulary size!