Build GPT · 1 of 10 · Python

Merge a frequent token pair

A GPT does not read letters or whole words. It reads tokens, which are common pieces of text. Byte-pair encoding, or BPE, finds those pieces by itself. It starts with single characters and looks for the two neighbours that appear together most often. It glues that pair into one new token, everywhere, and repeats. Frequent words end up as one token, and rare words are spelled out from smaller pieces.

Do the exercise in the app

Learn it

Words to know

token: One unit of text as the model sees it: a character, a piece of a word or a whole word.
byte-pair encoding: A way to build tokens: start from characters and keep merging the most frequent neighbouring pair.
vocabulary: The full list of tokens a model knows. A token's place in the list gives its ID.

How it works

List every pair of neighbours in the sequence and count how often each pair appears.
Pick the pair with the highest count. If several pairs share the top count, pick the one that appears first.
Walk through the sequence from the left. Wherever that pair appears, replace its two tokens with one joined token and jump past both.
This exercise does one such merge. A real tokenizer repeats it thousands of times and saves the list of merges.

Worked example

Input
tokens = ["l", "o", "w", "l", "o", "w", "e", "r"]

Output
["lo", "w", "lo", "w", "e", "r"]

Pair	Count	First seen at
l o	2	position 0
o w	2	position 1
w l	1	position 2
w e	1	position 5
e r	1	position 6

Two pairs share the top count of 2. The pair of l and o comes first, so it is merged, and the result is lo, w, lo, w, e, r.

Why it matters

The token IDs a GPT reads and writes come from a tokenizer trained this way. The next two lessons build the simpler character tokenizer that the workshop's GPT uses.

Your turn

Do one byte-pair merge on a list of tokens.

tokens: a list of strings; may be empty
Returns: A new list in which the most frequent neighbouring pair is replaced by the two strings joined, wherever it appears, scanning from the left without overlaps. Ties go to the pair that appears first. A list shorter than 2 comes back unchanged.

Example 1

Input
tokens = ["l", "o", "w", "l", "o", "w", "e", "r"]

Output
["lo", "w", "lo", "w", "e", "r"]

l o and o w both appear twice. l o is seen first, so both of its occurrences are merged.

Example 2

Input
tokens = ["a", "b", "a", "b", "c"]

Output
["ab", "ab", "c"]

a b appears twice and every other pair once.

Example 3

Input
tokens = ["b", "a", "c", "b", "a", "c"]

Output
["ba", "c", "ba", "c"]

b a and a c both appear twice. b a is seen first, so it is merged, although a c comes first in the alphabet.

Example 4

Input
tokens = ["a", "a", "a"]

Output
["aa", "a"]

The pair a a overlaps itself. Scanning from the left, the first two are merged and the third is left alone.

Example 5

Input
tokens = []

Output
[]

An empty list has no pairs, so it comes back unchanged.

Hints

Each hint gives away a little more. Open one only when you need it.

Hint 1: Where to start
Two separate passes: one to choose the pair, one to rebuild the list with that pair merged.
Hint 2: The key step
zip(tokens, tokens[1:]) gives every neighbouring pair. A Counter of those, with max(counts, key=counts.get), picks the most frequent, and on a tie the one counted first.
Hint 3: The outline
If there are fewer than 2 tokens, return a copy. After choosing pair, walk an index i through tokens. If i + 1 is still inside the list and tokens[i], tokens[i + 1] match the pair, append them joined and add 2 to i. Otherwise append tokens[i] and add 1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Step by step

With fewer than two tokens there is no pair to merge. max of an empty count would raise an error. Returning a copy keeps the caller's list untouched.
Count every neighbouring pair and take the most frequent. A Counter remembers the order in which it first saw each pair, and max returns the first of several equal counts. Together they give the tie rule.
Rebuild the list, joining the pair wherever it appears. Jumping two places after a merge is what makes the matches non-overlapping: a token used in one merge cannot be used in the next.

The same numbered steps are the comments in the solution.

Python

from collections import Counter


def solve(tokens):
    # 1. With fewer than two tokens there is no pair to merge
    if len(tokens) < 2:
        return list(tokens)
    # 2. Count every neighbouring pair and take the most frequent
    counts = Counter(zip(tokens, tokens[1:]))
    pair = max(counts, key=counts.get)
    # 3. Rebuild the list, joining the pair wherever it appears
    merged = []
    i = 0
    while i < len(tokens):
        if i + 1 < len(tokens) and (tokens[i], tokens[i + 1]) == pair:
            merged.append(tokens[i] + tokens[i + 1])
            i += 2
        else:
            merged.append(tokens[i])
            i += 1
    return merged

Watch out

Check i + 1 < len(tokens) before looking at tokens[i + 1]. On the last token there is no neighbour to read.
After a merge, move forward by 2. Moving by 1 would let a a a use the middle a in two merges.

Check yourself

What does one BPE merge step do?

It finds the most frequent pair of neighbouring tokens and replaces every occurrence of it with one joined token.

Why do common words end up as single tokens?

Their letter pairs are frequent, so they are merged early and then merged again, until the whole word is one token.