codeloopback
Guide contents

Lesson 7 of 73

Building a BPE Tokenizer

The previous lesson showed that the best way to cut text into tokens is a vocabulary of single bytes plus larger learned pieces. This lesson shows how those pieces are learned. The method is called byte-pair encoding, or BPE. It is behind most vocabularies used by Llama, Qwen, GPT, and DeepSeek models.

The idea is short. Start with the 256 possible byte values as the vocabulary. Look at a large body of text, find the two neighboring tokens that appear together most often, and glue them into one new token. Repeat until the vocabulary has the wanted size. Pieces that occur often, such as the or ing, end up as single tokens without anyone writing them down.

The lesson builds this algorithm in Java in small steps, then combines the steps into a Tokenizer class (Project 1). After it you can train a tokenizer on a text file, encode and decode with it, explain every field of a real tokenizer.ggml.merges list, and say why the symbol Ġ appears in vocabulary files.

Step Example
Count pairs, merge the top pair 1 and 2
Train a merge table, encode, decode 3 to 5
Cut text into chunks first (pre-tokenization with regular expressions) 6 and 7
The byte-to-unicode map and the Ġ symbol 8
Special tokens are handled before BPE 9
How much work encoding costs, and a faster method 10
Save, load, and round-trip test 11 and 12
SentencePiece and WordPiece conventions 13
Project 1: the Tokenizer class 14

Lesson 6 explained why a vocabulary of bytes plus learned pieces is useful: nothing is unknown, common text is short, and rare text falls back to bytes. This lesson shows how the pieces are learned.

The algorithm in four lines

Training takes a text and a number of merges. A merge is one decision of the form "from now on, treat this pair of neighboring tokens as one new token".

  1. Convert the text to a list of token ids, one per UTF-8 byte (ids 0 to 255).
  2. Count every pair of neighboring ids.
  3. Take the most frequent pair, give it the next unused id (256, then 257, and so on), and replace every occurrence of the pair with the new id. Record the merge.
  4. Repeat from step 2 until the wanted number of merges is done.

Here is one round on the string aaabdaaabac, with letters standing for their byte ids. The pair aa is the most frequent, so it becomes the new token X (id 256), and the text gets shorter:

Text
before: a a a b d a a a b a c      (11 tokens)
pair counts: aa=4, ab=2, others=1
merge aa -> X
after:  X a b d X a b a c          (9 tokens)

The list of merges, in order, is the whole tokenizer except for the 256 bytes. The vocabulary size is 256 + number of merges (plus special tokens). Encoding a new text applies the recorded merges in the same order. Decoding maps every id to its bytes and joins them.

Example 1: count adjacent pairs

Step 2 of the algorithm needs a count of neighboring pairs. This program counts them in aaabdaaabac, a classic test string, and prints them from most to least frequent. Pairs may overlap, so the text aaa contains the pair aa twice (at positions 0 and 1).

Java
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class PairCount {
    public static void main(String[] args) {
        String text = "aaabdaaabac";
        List<Integer> ids = new ArrayList<>();
        for (byte b : text.getBytes()) ids.add(b & 0xFF);
        Map<String, Integer> counts = new TreeMap<>();
        for (int i = 0; i + 1 < ids.size(); i++) {
            counts.merge("" + (char) (int) ids.get(i) + (char) (int) ids.get(i + 1), 1, Integer::sum);
        }
        counts.entrySet().stream()
            .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
            .forEach(e -> System.out.println("pair [" + e.getKey() + "] count " + e.getValue()));
        System.out.println("pairs in total = " + (ids.size() - 1));
    }
}
Output
pair [aa] count 4
pair [ab] count 2
pair [ac] count 1
pair [ba] count 1
pair [bd] count 1
pair [da] count 1
pairs in total = 10

The pair aa has count 4, ab has 2, and the other four pairs have 1 each. You can check the 4 by hand: the text starts with aaa, which holds 2 overlapping aa pairs, and aaab appears twice in the string.

The counts add up to 10, one fewer than the 11 bytes, because a list of 11 items has 10 neighboring pairs. The most frequent pair, aa, is the first merge. Counting overlapping pairs is deliberate. In aaa, the pair at positions 0 and 1 and the pair at positions 1 and 2 overlap, and the merge step decides which one wins.

Example 2: merge the most frequent pair

A merge replaces every occurrence of a pair with a new id. The scan goes from left to right, and a position is never used twice. This program merges the pair (a, a) into the id 256, prints the ids before and after, and then merges aaa to show how overlap is resolved.

Java
import java.util.ArrayList;
import java.util.List;

public class MergeStep {
    static List<Integer> merge(List<Integer> ids, int left, int right, int newId) {
        List<Integer> out = new ArrayList<>();
        int i = 0;
        while (i < ids.size()) {
            if (i + 1 < ids.size() && ids.get(i) == left && ids.get(i + 1) == right) {
                out.add(newId);
                i += 2;
            } else {
                out.add(ids.get(i));
                i++;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : "aaabdaaabac".getBytes()) ids.add(b & 0xFF);
        System.out.println("before: " + ids);
        List<Integer> merged = merge(ids, 'a', 'a', 256);
        System.out.println("after : " + merged);
        System.out.println("length " + ids.size() + " -> " + merged.size());
        System.out.println("aaa with (a,a) -> " + merge(List.of(97, 97, 97), 'a', 'a', 256));
    }
}
Output
before: [97, 97, 97, 98, 100, 97, 97, 97, 98, 97, 99]
after : [256, 97, 98, 100, 256, 97, 98, 97, 99]
length 11 -> 9
aaa with (a,a) -> [256, 97]

Every aa became id 256, so the text shrank from 11 ids to 9. Ids 0 to 255 are bytes, so 256 is the first learned token.

The last line shows how overlap is resolved. In aaa, the scan from the left merges the first two letters and leaves the third, giving [256, 97]. The scan then moves past both merged positions, so the middle a is not used again.

Example 3: the training loop

Training is the loop from the four lines above: count, pick the winner, merge, and record. The classic training text for BPE examples has words that share pieces: low, lower, newest, widest.

The program trains 10 merges on the raw bytes of this text, so spaces take part in merges. For every merge it prints the two ids that were joined, the new id, the text of the new token, how many times the pair occurred, and how long the text is afterwards. A space is shown as _. The vocabulary is a list of byte strings: entries 0 to 255 are single bytes, and each merge appends the two joined byte strings.

Java
import java.io.ByteArrayOutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Train {
    public static void main(String[] args) {
        String text = "low low low low low lower lower newest newest newest newest newest newest widest widest widest";
        List<Integer> ids = new ArrayList<>();
        for (byte b : text.getBytes()) ids.add(b & 0xFF);
        List<byte[]> vocab = new ArrayList<>();
        for (int i = 0; i < 256; i++) vocab.add(new byte[] {(byte) i});
        System.out.println("text bytes = " + ids.size());
        for (int m = 0; m < 10; m++) {
            Map<Long, Integer> counts = new HashMap<>();
            for (int i = 0; i + 1 < ids.size(); i++) counts.merge(((long) ids.get(i) << 32) | ids.get(i + 1), 1, Integer::sum);
            long best = -1;
            int bestCount = 0;
            for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
            }
            int left = (int) (best >> 32), right = (int) best, newId = vocab.size();
            ByteArrayOutputStream joined = new ByteArrayOutputStream();
            joined.writeBytes(vocab.get(left));
            joined.writeBytes(vocab.get(right));
            vocab.add(joined.toByteArray());
            List<Integer> next = new ArrayList<>();
            for (int i = 0; i < ids.size(); i++) {
                if (i + 1 < ids.size() && ids.get(i) == left && ids.get(i + 1) == right) { next.add(newId); i++; }
                else next.add(ids.get(i));
            }
            ids = next;
            System.out.println(String.format("merge %2d: %3d + %3d -> %d  %-8s count %2d  text length now %d", m, left, right, newId,
                "[" + new String(vocab.get(newId)).replace(' ', '_') + "]", bestCount, ids.size()));
        }
    }
}
Output
text bytes = 94
merge  0: 101 + 115 -> 256  [es]     count  9  text length now 85
merge  1: 256 + 116 -> 257  [est]    count  9  text length now 76
merge  2: 257 +  32 -> 258  [est_]   count  8  text length now 68
merge  3: 108 + 111 -> 259  [lo]     count  7  text length now 61
merge  4: 259 + 119 -> 260  [low]    count  7  text length now 54
merge  5:  32 + 260 -> 261  [_low]   count  6  text length now 48
merge  6: 101 + 119 -> 262  [ew]     count  6  text length now 42
merge  7: 110 + 262 -> 263  [new]    count  6  text length now 36
merge  8: 263 + 258 -> 264  [newest_] count  6  text length now 30
merge  9: 264 + 264 -> 265  [newest_newest_] count  5  text length now 27

Read the lines from the top. The first merges are the endings that repeat most. es occurs 9 times: 6 times in newest and 3 times in widest. Each merge removes one id per occurrence, so the text shrinks from 94 bytes to 94 - 9 = 85 ids. Then come est, and est_ with its trailing space. After that come lo, low, and _low.

Later merges are longer pieces built from earlier pieces. For example, newest_ is made from new (id 263) and est_ (id 258). A merge can use an id that an earlier merge created. This is how long pieces appear without being searched for directly. After 10 merges the text has 27 ids.

The last merge, newest_newest_, shows a quirk of training on a tiny text without cutting it into words first. The text repeats newest six times in a row, so the pair of two such tokens wins. Pre-tokenization (Example 6) prevents this kind of merge.

When two pairs have the same count, the code picks the one with the smaller pair key, so the output is the same on every run. Real trainers also need a fixed tie-break rule.

Example 4: encode new text by merge rank

Encoding must reproduce what training did, because the model was trained with exactly those token boundaries. The merge table gives each pair a rank: the position of its merge in the training order, where 0 is the first merge. To encode a text:

  1. Start from its bytes.
  2. Among all neighboring pairs present, find the one with the lowest rank, and merge all its occurrences.
  3. Repeat until no neighboring pair has a rank.

The program contains a small Bpe class (trained as in Example 3, restated compactly, with a rule to stop when the best pair occurs fewer than 2 times) and encodes three texts, one of which uses words the training text never contained.

Java
import java.io.ByteArrayOutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Encode {
    static class Bpe {
        final List<int[]> merges = new ArrayList<>();
        final Map<Long, Integer> rank = new HashMap<>();
        final List<byte[]> vocab = new ArrayList<>();

        Bpe() { for (int i = 0; i < 256; i++) vocab.add(new byte[] {(byte) i}); }

        static long key(int a, int b) { return ((long) a << 32) | b; }

        static List<Integer> merge(List<Integer> ids, int left, int right, int newId) {
            List<Integer> out = new ArrayList<>();
            for (int i = 0; i < ids.size(); i++) {
                if (i + 1 < ids.size() && ids.get(i) == left && ids.get(i + 1) == right) { out.add(newId); i++; }
                else out.add(ids.get(i));
            }
            return out;
        }

        void train(String text, int count) {
            List<Integer> ids = bytes(text);
            for (int m = 0; m < count; m++) {
                Map<Long, Integer> counts = new HashMap<>();
                for (int i = 0; i + 1 < ids.size(); i++) counts.merge(key(ids.get(i), ids.get(i + 1)), 1, Integer::sum);
                long best = -1;
                int bestCount = 0;
                for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                    if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
                }
                if (bestCount < 2) break;
                addMerge((int) (best >> 32), (int) best);
                ids = merge(ids, (int) (best >> 32), (int) best, vocab.size() - 1);
            }
        }

        void addMerge(int left, int right) {
            ByteArrayOutputStream joined = new ByteArrayOutputStream();
            joined.writeBytes(vocab.get(left));
            joined.writeBytes(vocab.get(right));
            rank.put(key(left, right), merges.size());
            merges.add(new int[] {left, right});
            vocab.add(joined.toByteArray());
        }

        static List<Integer> bytes(String text) {
            List<Integer> ids = new ArrayList<>();
            for (byte b : text.getBytes(java.nio.charset.StandardCharsets.UTF_8)) ids.add(b & 0xFF);
            return ids;
        }

        List<Integer> encode(String text) {
            List<Integer> ids = bytes(text);
            while (true) {
                int bestRank = Integer.MAX_VALUE, bestPos = -1;
                for (int i = 0; i + 1 < ids.size(); i++) {
                    int r = rank.getOrDefault(key(ids.get(i), ids.get(i + 1)), Integer.MAX_VALUE);
                    if (r < bestRank) { bestRank = r; bestPos = i; }
                }
                if (bestPos < 0) return ids;
                ids = merge(ids, ids.get(bestPos), ids.get(bestPos + 1), 256 + bestRank);
            }
        }

        String piece(int id) { return new String(vocab.get(id), java.nio.charset.StandardCharsets.UTF_8).replace(' ', '_'); }
    }

    public static void main(String[] args) {
        Bpe bpe = new Bpe();
        bpe.train("low low low low low lower lower newest newest newest newest newest newest widest widest widest", 10);
        for (String s : new String[] {"lowest", "newer low", "wider"}) {
            List<Integer> ids = bpe.encode(s);
            StringBuilder pieces = new StringBuilder();
            for (int id : ids) pieces.append('[').append(bpe.piece(id)).append(']');
            System.out.println(String.format("%-10s %2d bytes -> %d tokens %s %s", "\"" + s + "\"", s.length(), ids.size(), ids, pieces));
        }
    }
}
Output
"lowest"    6 bytes -> 2 tokens [260, 257] [low][est]
"newer low"  9 bytes -> 4 tokens [263, 101, 114, 261] [new][e][r][_low]
"wider"     5 bytes -> 5 tokens [119, 105, 100, 101, 114] [w][i][d][e][r]

lowest becomes 2 tokens, [low][est]. The word was not in the training text, but its pieces were. The encoder found the lowest-rank pair present (es, rank 0), then est (rank 1), then lo and low.

newer low becomes 4 tokens: [new] (made by merge 7), then e and r as plain bytes, then [_low]. The word wider stays as 5 single bytes, because none of its neighboring pairs was ever merged during training.

Text the tokenizer did not see in training costs more tokens. This is the same effect as the whole-word versus fallback behavior from lesson 6. The rule that keeps encoding identical to training is to always apply the lowest-rank merge first.

Example 5: decode ids back to text

Decoding is simpler than encoding and does not need the merge rules. Every id has a byte string: a single byte for ids below 256, and the joined bytes of its two parts for merged ids. Decoding joins the byte strings of all ids and decodes the result as UTF-8.

The decode step must work on the joined bytes and not on separate pieces, because one character can be spread over several tokens (lesson 6, Example 11). This program rebuilds the vocabulary from the 10 merges of Example 3 and decodes a list of ids. It then shows that decoding one byte of the 3-byte euro sign gives garbage, while decoding all three bytes together gives the character.

Java
import java.io.ByteArrayOutputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;

public class Decode {
    public static void main(String[] args) {
        // The 10 merges printed by Example 3, as (left, right) id pairs. The first one creates id 256.
        int[][] merges = {{101, 115}, {256, 116}, {257, 32}, {108, 111}, {259, 119},
                          {32, 260}, {101, 119}, {110, 262}, {263, 258}, {264, 264}};
        List<byte[]> vocab = new ArrayList<>();
        for (int i = 0; i < 256; i++) vocab.add(new byte[] {(byte) i});
        for (int[] m : merges) {
            ByteArrayOutputStream joined = new ByteArrayOutputStream();
            joined.writeBytes(vocab.get(m[0]));
            joined.writeBytes(vocab.get(m[1]));
            vocab.add(joined.toByteArray());
        }
        List<Integer> ids = List.of(263, 101, 114, 261);
        ByteArrayOutputStream all = new ByteArrayOutputStream();
        for (int id : ids) all.writeBytes(vocab.get(id));
        System.out.println("ids " + ids + " -> \"" + new String(all.toByteArray(), StandardCharsets.UTF_8) + "\"");

        byte[] euro = "\u20ac".getBytes(StandardCharsets.UTF_8);
        System.out.println("the euro sign has " + euro.length + " bytes");
        for (byte b : euro) {
            System.out.println("  one byte alone -> code " + (int) new String(new byte[] {b}, StandardCharsets.UTF_8).charAt(0) + " (65533 is the replacement character)");
        }
        System.out.println("all bytes together -> " + new String(euro, StandardCharsets.UTF_8));
    }
}
Output
ids [263, 101, 114, 261] -> "newer low"
the euro sign has 3 bytes
  one byte alone -> code 65533 (65533 is the replacement character)
  one byte alone -> code 65533 (65533 is the replacement character)
  one byte alone -> code 65533 (65533 is the replacement character)
all bytes together -> €

The ids [263, 101, 114, 261] decode to newer low: new + e + r + _low. The vocabulary was rebuilt from the merge list alone, and decoding is a lookup followed by a concatenation.

The euro sign € has 3 bytes. Decoded one byte at a time, each gives the replacement character (code 65533). Decoded together, the three bytes give €. A decoder must therefore join bytes first and decode text last. A streaming decoder must hold incomplete bytes back (lesson 6, Example 11).

Example 6: pre-tokenization with a regular expression

In Example 3, merges could join the end of one word with the start of the next, such as a final t, a space, and the next letter. This wastes vocabulary on pieces that mix two words and have little meaning on their own.

Production tokenizers solve this by first cutting the text into chunks with a regular expression (a text-matching pattern), and then running BPE inside each chunk only. This step is called pre-tokenization. Merges can never cross a chunk border, so a token never holds half of one word and half of another. The pre-tokenizer also decides how digits and punctuation are grouped.

The program applies three real patterns to two texts and prints the chunks. The Llama 3 and Qwen2 patterns are copied from the pinned llama.cpp source (src/llama-vocab.cpp). The GPT-2 pattern is the original one from GPT-2. llama.cpp's copy of it leaves out the final |\s+ alternative. In the patterns, \p{L} matches a letter and \p{N} matches a digit, in any script. In the output a space shows as _ and a newline as \n.

Java
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class PreTokenize {
    static final String CONTRACTION = "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])";
    static final String GPT2 = "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+";
    static final String LLAMA3 = CONTRACTION + "|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";
    static final String QWEN2 = CONTRACTION + "|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";

    static String show(String pattern, String text) {
        Matcher m = Pattern.compile(pattern).matcher(text);
        List<String> parts = new ArrayList<>();
        while (m.find()) parts.add(m.group().replace(' ', '_').replace("\n", "\\n"));
        return String.join(" | ", parts);
    }

    public static void main(String[] args) {
        String[] texts = {"Hello, world! It's 2026.", "x = 12345;\n    return x;"};
        for (String text : texts) {
            System.out.println("text   : " + text.replace("\n", "\\n"));
            System.out.println("GPT-2  : " + show(GPT2, text));
            System.out.println("Llama 3: " + show(LLAMA3, text));
            System.out.println("Qwen2  : " + show(QWEN2, text));
            System.out.println();
        }
    }
}
Output
text   : Hello, world! It's 2026.
GPT-2  : Hello | , | _world | ! | _It | 's | _2026 | .
Llama 3: Hello | , | _world | ! | _It | 's | _ | 202 | 6 | .
Qwen2  : Hello | , | _world | ! | _It | 's | _ | 2 | 0 | 2 | 6 | .

text   : x = 12345;\n    return x;
GPT-2  : x | _= | _12345 | ; | \n___ | _return | _x | ;
Llama 3: x | _= | _ | 123 | 45 | ;\n | ___ | _return | _x | ;
Qwen2  : x | _= | _ | 1 | 2 | 3 | 4 | 5 | ;\n | ___ | _return | _x | ;

The three patterns agree on words and punctuation: Hello, ,, _world, !. The leading space belongs to the word that follows (_world, _It). This is why Hello and Hello are different tokens (lesson 6).

The patterns differ on digits, and the output shows the same differences as the real counts in lesson 6:

  • GPT-2 keeps a whole number in one chunk (_2026, _12345).
  • Llama 3 splits digits into groups of up to three from the left (202, 6 and 123, 45), because of the pattern part \p{N}{1,3}.
  • Qwen2 puts every digit in its own chunk, because of \p{N}.

The second text shows whitespace. In GPT-2, \n___ is one chunk, a newline plus the indentation. Llama 3 and Qwen2 attach the newline to the preceding punctuation (;\n) and leave the indentation spaces as ___ before _return. Since BPE runs inside each chunk, a merge can never create a token that spans two chunks.

Example 7: train on chunks with counts

Training on chunks is faster than training on the whole text, for a simple reason. Real text repeats the same words many times. Each distinct chunk can be stored once with a count, and a pair inside it is counted count times at once, instead of re-reading the word every time it occurs.

The program cuts a text with the GPT-2 pattern, counts each distinct chunk, and trains 14 merges. A space shown as _ belongs to the start of the chunk that follows it. At the end it prints how many tokens each distinct chunk needs after training.

Java
import java.io.ByteArrayOutputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TrainChunks {
    public static void main(String[] args) {
        String text = "the cat sat on the mat. the dog sat on the log. the cat saw the dog. the dog saw the cat.";
        Matcher m = Pattern.compile("'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+").matcher(text);
        Map<String, Integer> chunkCounts = new TreeMap<>();
        int total = 0;
        while (m.find()) { chunkCounts.merge(m.group(), 1, Integer::sum); total++; }
        System.out.println("chunks = " + total + ", distinct chunks = " + chunkCounts.size());

        List<int[]> words = new ArrayList<>();
        List<Integer> weights = new ArrayList<>();
        for (Map.Entry<String, Integer> e : chunkCounts.entrySet()) {
            byte[] b = e.getKey().getBytes(StandardCharsets.UTF_8);
            int[] w = new int[b.length];
            for (int i = 0; i < b.length; i++) w[i] = b[i] & 0xFF;
            words.add(w);
            weights.add(e.getValue());
        }
        List<byte[]> vocab = new ArrayList<>();
        for (int i = 0; i < 256; i++) vocab.add(new byte[] {(byte) i});
        for (int step = 0; step < 14; step++) {
            Map<Long, Integer> counts = new HashMap<>();
            for (int k = 0; k < words.size(); k++) {
                int[] w = words.get(k);
                for (int i = 0; i + 1 < w.length; i++) counts.merge(((long) w[i] << 32) | w[i + 1], weights.get(k), Integer::sum);
            }
            long best = -1;
            int bestCount = 0;
            for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
            }
            if (bestCount == 0) break;
            int left = (int) (best >> 32), right = (int) best, id = vocab.size();
            ByteArrayOutputStream joined = new ByteArrayOutputStream();
            joined.writeBytes(vocab.get(left));
            joined.writeBytes(vocab.get(right));
            vocab.add(joined.toByteArray());
            for (int k = 0; k < words.size(); k++) {
                int[] w = words.get(k);
                List<Integer> out = new ArrayList<>();
                for (int i = 0; i < w.length; i++) {
                    if (i + 1 < w.length && w[i] == left && w[i + 1] == right) { out.add(id); i++; } else out.add(w[i]);
                }
                words.set(k, out.stream().mapToInt(Integer::intValue).toArray());
            }
            System.out.println(String.format("merge %2d -> %d [%s] count %d", step, id, new String(vocab.get(id), StandardCharsets.UTF_8).replace(' ', '_'), bestCount));
        }
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        for (String chunk : chunkCounts.keySet()) {
            sb.append(chunk.replace(' ', '_')).append('=').append(words.get(idx++).length).append(' ');
        }
        System.out.println("tokens per distinct chunk after training: " + sb.toString().trim());
    }
}
Output
chunks = 26, distinct chunks = 10
merge  0 -> 256 [he] count 8
merge  1 -> 257 [the] count 8
merge  2 -> 258 [_the] count 7
merge  3 -> 259 [at] count 6
merge  4 -> 260 [_s] count 4
merge  5 -> 261 [og] count 4
merge  6 -> 262 [_c] count 3
merge  7 -> 263 [_d] count 3
merge  8 -> 264 [_cat] count 3
merge  9 -> 265 [_dog] count 3
merge 10 -> 266 [_o] count 2
merge 11 -> 267 [aw] count 2
merge 12 -> 268 [_sat] count 2
merge 13 -> 269 [_saw] count 2
tokens per distinct chunk after training: _cat=1 _dog=1 _log=3 _mat=3 _on=2 _sat=1 _saw=1 _the=1 .=1 the=1

The text has 26 chunks but only 10 distinct ones, so the trainer handles 10 short words with counts and not 26 words one by one. The first merge, he, has count 8 because the and _the appear 8 times in total. Then the, _the, at, and _s follow.

Whole words become single tokens when they are frequent enough. _cat, _dog, _sat, _saw, _the, and the all end with 1 token. A rarer word, _log, needs 3 tokens (_, l, og), and _mat needs 3 (_, m, at).

The merges never join . with a word, because the chunks keep them apart. A real trainer repeats this loop 100,000 times or more on gigabytes of text.

Example 8: the byte-to-unicode map and Ġ

If you open a real vocabulary file, you find odd symbols such as Ġworld and Ċ. They come from a storage problem. GPT-2 stored its merge rules as text lines, so every byte needed a printable character. Invisible bytes such as space and newline would break the file format.

Its fix is a fixed map from the 256 byte values to 256 distinct visible characters:

  • The printable ASCII bytes (! to ~) map to themselves.
  • Two ranges of printable Latin-1 characters (¡ to ¬ and ® to ÿ) also map to themselves.
  • The remaining 68 bytes (control characters, space, delete, and a few Latin-1 characters) map in order to the code points 256, 257, and so on.

The gguf-py library has the same function (bytes_to_unicode in gguf/vocab.py). This program builds the map, prints its size, prints the result for nine byte values, and shows five strings as they look through the map.

Java
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ByteToUnicode {
    static Map<Integer, Character> build() {
        List<Integer> bs = new ArrayList<>();
        for (int b = '!'; b <= '~'; b++) bs.add(b);
        for (int b = 0xA1; b <= 0xAC; b++) bs.add(b);
        for (int b = 0xAE; b <= 0xFF; b++) bs.add(b);
        Map<Integer, Character> map = new TreeMap<>();
        for (int b : bs) map.put(b, (char) b);
        int n = 0;
        for (int b = 0; b < 256; b++) {
            if (!map.containsKey(b)) map.put(b, (char) (256 + n++));
        }
        return map;
    }

    static String visible(Map<Integer, Character> map, String text) {
        StringBuilder sb = new StringBuilder();
        for (byte b : text.getBytes(StandardCharsets.UTF_8)) sb.append(map.get(b & 0xFF));
        return sb.toString();
    }

    public static void main(String[] args) {
        Map<Integer, Character> map = build();
        System.out.println("entries = " + map.size() + ", distinct characters = " + new HashSet<>(map.values()).size());
        for (int b : new int[] {9, 10, 32, 33, 65, 127, 173, 195, 255}) {
            System.out.println(String.format("byte %3d -> U+%04X %s", b, (int) map.get(b), map.get(b)));
        }
        for (String s : new String[] {" world", "\n", "        ", " 😀", "世界"}) {
            System.out.println("[" + s.replace("\n", "\\n") + "] -> " + visible(map, s));
        }
    }
}
Output
entries = 256, distinct characters = 256
byte   9 -> U+0109 ĉ
byte  10 -> U+010A Ċ
byte  32 -> U+0120 Ġ
byte  33 -> U+0021 !
byte  65 -> U+0041 A
byte 127 -> U+0121 ġ
byte 173 -> U+0143 Ń
byte 195 -> U+00C3 Ã
byte 255 -> U+00FF ÿ
[ world] -> Ġworld
[\n] -> Ċ
[        ] -> ĠĠĠĠĠĠĠĠ
[ 😀] -> ĠðŁĺĢ
[世界] -> ä¸ĸçķĮ

All 256 bytes get distinct visible characters, so no information is lost. The printable ASCII bytes map to themselves (! is !, A is A). The tab (byte 9) becomes ĉ, the newline (byte 10) becomes Ċ, and the space (byte 32) becomes Ġ, which is U+0120.

The arithmetic is regular. The map gives code point 256 to byte 0, 257 to byte 1, and so on in byte order, so the space, byte 32, gets 256 + 32 = 288, which is 0x120, or U+0120.

In the lower rows, ĠðŁĺĢ is the encoding of a space plus the four bytes of the emoji, and ä¸ĸçķĮ is 世界 seen through the map. These strings equal the ones stored in the real Qwen2 vocabulary: id 1879 is Ġworld, id 198 is Ċ, id 90316 is ĠðŁĺĢ, and id 99489 is ä¸ĸçķĮ, as read with gguf-py.

The map is only a way to write bytes as text. Decoding applies the reverse map, so Ġ always means the byte 32.

Example 9: special tokens are cut out before BPE

Special tokens (lesson 6) are never produced by merges, because they do not come from frequent byte pairs. The encoder handles them first. It splits the text on the special-token strings, turns each one into its reserved id, and runs BPE only on the text between them.

A regular expression built from the special strings, longest first, does the split. This program splits a Qwen-style chat string and shows the ids. The ordinary text between special tokens is turned into plain byte ids, because the point here is the split. A real tokenizer replaces encodeText with the merge-rank encoder of Example 4. The program also encodes <|im_end|> with special parsing off, and counts the special ids.

Java
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SplitSpecials {
    static final Map<String, Integer> SPECIAL = new TreeMap<>(Map.of("<|im_start|>", 300, "<|im_end|>", 301, "<|endoftext|>", 302));

    static List<Integer> encodeText(String text) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : text.getBytes(StandardCharsets.UTF_8)) ids.add(b & 0xFF);
        return ids;
    }

    static List<Integer> encode(String text, boolean parseSpecial) {
        if (!parseSpecial) return encodeText(text);
        List<String> keys = new ArrayList<>(SPECIAL.keySet());
        keys.sort(Comparator.comparingInt(String::length).reversed());
        StringBuilder regex = new StringBuilder();
        for (String k : keys) regex.append(regex.length() == 0 ? "" : "|").append(Pattern.quote(k));
        Matcher m = Pattern.compile(regex.toString()).matcher(text);
        List<Integer> ids = new ArrayList<>();
        int last = 0;
        while (m.find()) {
            ids.addAll(encodeText(text.substring(last, m.start())));
            ids.add(SPECIAL.get(m.group()));
            last = m.end();
        }
        ids.addAll(encodeText(text.substring(last)));
        return ids;
    }

    public static void main(String[] args) {
        String chat = "<|im_start|>user\nHi<|im_end|>\n<|im_start|>assistant\n";
        System.out.println("parse special : " + encode(chat, true));
        System.out.println("plain text    : " + encode("<|im_end|>", false));
        System.out.println("special ids   : " + encode(chat, true).stream().filter(i -> i >= 256).count());
    }
}
Output
parse special : [300, 117, 115, 101, 114, 10, 72, 105, 301, 10, 300, 97, 115, 115, 105, 115, 116, 97, 110, 116, 10]
plain text    : [60, 124, 105, 109, 95, 101, 110, 100, 124, 62]
special ids   : 3

The chat string splits into three special tokens (300 for <|im_start|> twice and 301 for <|im_end|>) and the bytes of the text between them: user\n, Hi, \n, and assistant\n. The ids 117, 115, 101, 114 spell user.

With parsing off, <|im_end|> becomes the 10 bytes of its characters and no special id appears. This is the safe way to encode user text (lesson 6, Example 7).

Longer special strings are tried first. This way, a special token that is a prefix of another one cannot hide it.

Example 10: encoding cost

The encoder of Example 4 scans the whole list again after every merge. For a chunk of n tokens, that is up to n rounds, each doing up to n pair lookups, so about n * n work. This is called quadratic growth: a chunk 10 times longer costs about 100 times more.

Real chunks are short (single words), so this is acceptable. But a chunk can be long, such as a minified file or a long string of letters with no spaces. The standard fix keeps the tokens in a doubly linked list, so neighbors can be found and removed quickly, and keeps the candidate pairs in a priority queue ordered by rank. A merge then changes at most two candidate pairs, so the work grows like n log n.

The program trains 300 merges on 20,000 random letters from a 4-letter alphabet. The generator is seeded, so the output is the same every run. It then encodes strings of three lengths with both methods. It counts pair lookups for the scan and queue operations (pushes and pops) for the queue, checks that both give the same ids, and prints the counts. Counts, not times, make the result deterministic.

Java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;

public class EncodeCost {
    record Cand(int rank, int pos, int left, int right) {}

    static final Map<Long, Integer> RANK = new HashMap<>();
    static long ops;

    static long key(int a, int b) { return ((long) a << 32) | b; }

    static void train(String text, int merges) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : text.getBytes()) ids.add(b & 0xFF);
        for (int m = 0; m < merges; m++) {
            Map<Long, Integer> counts = new HashMap<>();
            for (int i = 0; i + 1 < ids.size(); i++) counts.merge(key(ids.get(i), ids.get(i + 1)), 1, Integer::sum);
            long best = -1;
            int bestCount = 0;
            for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
            }
            RANK.put(best, m);
            List<Integer> next = new ArrayList<>();
            for (int i = 0; i < ids.size(); i++) {
                if (i + 1 < ids.size() && key(ids.get(i), ids.get(i + 1)) == best) { next.add(256 + m); i++; } else next.add(ids.get(i));
            }
            ids = next;
        }
    }

    static List<Integer> scan(String text) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : text.getBytes()) ids.add(b & 0xFF);
        ops = 0;
        while (true) {
            int bestRank = Integer.MAX_VALUE;
            long bestKey = -1;
            for (int i = 0; i + 1 < ids.size(); i++) {
                ops++;
                int r = RANK.getOrDefault(key(ids.get(i), ids.get(i + 1)), Integer.MAX_VALUE);
                if (r < bestRank) { bestRank = r; bestKey = key(ids.get(i), ids.get(i + 1)); }
            }
            if (bestRank == Integer.MAX_VALUE) return ids;
            List<Integer> next = new ArrayList<>();
            for (int i = 0; i < ids.size(); i++) {
                if (i + 1 < ids.size() && key(ids.get(i), ids.get(i + 1)) == bestKey) { next.add(256 + bestRank); i++; } else next.add(ids.get(i));
            }
            ids = next;
        }
    }

    static List<Integer> queue(String text) {
        byte[] bytes = text.getBytes();
        int n = bytes.length;
        int[] id = new int[n], next = new int[n], prev = new int[n];
        boolean[] alive = new boolean[n];
        for (int i = 0; i < n; i++) { id[i] = bytes[i] & 0xFF; prev[i] = i - 1; next[i] = i + 1 < n ? i + 1 : -1; alive[i] = true; }
        PriorityQueue<Cand> pq = new PriorityQueue<>(Comparator.comparingInt(Cand::rank).thenComparingInt(Cand::pos));
        ops = 0;
        for (int i = 0; i + 1 < n; i++) push(pq, id, next, i);
        while (!pq.isEmpty()) {
            Cand c = pq.poll();
            ops++;
            int p = c.pos();
            if (!alive[p] || next[p] < 0 || id[p] != c.left() || id[next[p]] != c.right()) continue;
            int q = next[p];
            id[p] = 256 + c.rank();
            alive[q] = false;
            next[p] = next[q];
            if (next[q] >= 0) prev[next[q]] = p;
            if (prev[p] >= 0) push(pq, id, next, prev[p]);
            if (next[p] >= 0) push(pq, id, next, p);
        }
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i >= 0 && i < n; i = next[i] < 0 ? n : next[i]) if (alive[i]) out.add(id[i]);
        return out;
    }

    static void push(PriorityQueue<Cand> pq, int[] id, int[] next, int i) {
        Integer r = RANK.get(key(id[i], id[next[i]]));
        if (r != null) { pq.add(new Cand(r, i, id[i], id[next[i]])); ops++; }
    }

    static String letters(Random rnd, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append("abcd".charAt(rnd.nextInt(4)));
        return sb.toString();
    }

    public static void main(String[] args) {
        Random rnd = new Random(7);
        train(letters(rnd, 20_000), 300);
        System.out.println("merges learned = " + RANK.size());
        System.out.println("    n   tokens   scan lookups   queue operations   same result");
        for (int n : new int[] {200, 2000, 20000}) {
            String text = letters(rnd, n);
            List<Integer> a = scan(text);
            long scanOps = ops;
            List<Integer> b = queue(text);
            long queueOps = ops;
            System.out.println(String.format("%5d %8d %14d %18d   %s", n, a.size(), scanOps, queueOps, a.equals(b)));
        }
    }
}
Output
merges learned = 300
    n   tokens   scan lookups   queue operations   same result
  200       56           5385                496   true
 2000      601         130477               4948   true
20000     5910        2095430              49290   true

Both methods give the same ids in all three cases, so the queue is a correct replacement. Compare the growth of the two count columns:

  • The scan does 5,385 pair lookups for 200 bytes, 130,477 for 2,000, and 2,095,430 for 20,000. A 10 times longer text costs about 24 times more lookups (130,477 / 5,385), and then about 16 times more (2,095,430 / 130,477). Both the number of rounds and the length of each scan grow.
  • The queue does 496, 4,948, and 49,290 operations. It grows almost exactly 10 times for each 10 times more text.

At 20,000 bytes the queue does about 42 times fewer operations (2,095,430 / 49,290). Pre-tokenization keeps most chunks to a few bytes, so engines mostly meet short chunks. The BPE encoder in llama.cpp (src/llama-vocab.cpp) also keeps its candidate pairs in a priority queue. The point here is the difference in growth.

Example 11: save and load a tokenizer

A trained tokenizer is its merge list, so saving it means writing that list to a file. This program writes the merges of Example 3 to a text file: a version line, the special tokens, and then one line per merge with the two ids. It reads the file back and checks that the loaded list is equal. The vocabulary (the bytes of every id) is rebuilt from the merges on load, so it is not stored.

Real formats do the same in their own way. The GGUF file of Qwen2 stores tokenizer.ggml.merges as 151,387 text entries such as Ġ Ġ, ĠĠ ĠĠ, i n, and Ġ t, in rank order (read with gguf-py). A tokenizer.ggml.tokens list holds the text of every token.

Java
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;

public class SaveLoad {
    static void save(Path file, List<int[]> merges, List<String> specials) throws IOException {
        List<String> lines = new ArrayList<>();
        lines.add("#bpe v1");
        for (String s : specials) lines.add("special " + s);
        for (int[] m : merges) lines.add(m[0] + " " + m[1]);
        Files.write(file, lines);
    }

    static List<int[]> load(Path file, List<String> specialsOut) throws IOException {
        List<int[]> merges = new ArrayList<>();
        List<String> lines = Files.readAllLines(file);
        if (!lines.get(0).equals("#bpe v1")) throw new IOException("unknown format: " + lines.get(0));
        for (String line : lines.subList(1, lines.size())) {
            if (line.startsWith("special ")) specialsOut.add(line.substring(8));
            else {
                String[] p = line.split(" ");
                merges.add(new int[] {Integer.parseInt(p[0]), Integer.parseInt(p[1])});
            }
        }
        return merges;
    }

    public static void main(String[] args) throws IOException {
        List<int[]> merges = List.of(new int[] {101, 115}, new int[] {256, 116}, new int[] {257, 32}, new int[] {108, 111},
            new int[] {259, 119}, new int[] {32, 260}, new int[] {101, 119}, new int[] {110, 262}, new int[] {263, 258}, new int[] {264, 264});
        List<String> specials = List.of("<|endoftext|>");
        Path file = Files.createTempFile("bpe", ".txt");
        try {
            save(file, merges, specials);
            System.out.println(Files.readString(file).trim());
            List<String> loadedSpecials = new ArrayList<>();
            List<int[]> loaded = load(file, loadedSpecials);
            boolean same = loaded.size() == merges.size();
            for (int i = 0; i < merges.size() && same; i++) same = java.util.Arrays.equals(merges.get(i), loaded.get(i));
            System.out.println("merges equal after reload: " + same + ", specials: " + loadedSpecials);
            System.out.println("vocabulary size = " + (256 + loaded.size() + loadedSpecials.size()));
        } finally {
            Files.deleteIfExists(file);
        }
    }
}
Output
#bpe v1
special <|endoftext|>
101 115
256 116
257 32
108 111
259 119
32 260
101 119
110 262
263 258
264 264
merges equal after reload: true, specials: [<|endoftext|>]
vocabulary size = 267

The file has a version line, one line per special token, and one line per merge. The line 101 115 means "merge byte 101 (e) with byte 115 (s) into id 256". The next line, 256 116, means "merge 256 with byte 116 (t) into id 257". The merge order gives the ids, so the file does not need to list them.

The loaded list equals the saved list. The vocabulary size is 256 bytes plus 10 merges plus 1 special token, which is 267.

Storing ids makes the file independent of how a token is written as text. The GGUF format makes the opposite choice. It stores merges as the text of both pieces in the byte-to-unicode form (Ġ t for the merge of a space and t, Example 8). Both formats carry the same information. A loader must check the version line, because a file in an unknown format would otherwise load as garbage.

Example 12: a round-trip test on random strings

The most important test of a tokenizer is decode(encode(s)) == s for every string s. This is called a round trip. A byte-level tokenizer should pass it for any valid text, including emoji, mixed scripts, and control characters.

This program trains a small tokenizer (the compact version of Examples 3 to 5, with the GPT-2 pre-tokenizer pattern left out to keep the code short). It then tests 2,000 random strings built from a pool of pieces that includes accents, Chinese characters, an emoji, a multi-code-point emoji, tabs, and newlines. The generator is seeded, so the strings are the same every run. It prints the failure count and the average number of bytes per token.

Java
import java.io.ByteArrayOutputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class RoundTrip {
    static final List<byte[]> VOCAB = new ArrayList<>();
    static final Map<Long, Integer> RANK = new HashMap<>();

    static long key(int a, int b) { return ((long) a << 32) | b; }

    static List<Integer> bytes(String s) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) ids.add(b & 0xFF);
        return ids;
    }

    static List<Integer> applyMerge(List<Integer> ids, int l, int r, int id) {
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < ids.size(); i++) {
            if (i + 1 < ids.size() && ids.get(i) == l && ids.get(i + 1) == r) { out.add(id); i++; } else out.add(ids.get(i));
        }
        return out;
    }

    static void train(String text, int merges) {
        for (int i = 0; i < 256; i++) VOCAB.add(new byte[] {(byte) i});
        List<Integer> ids = bytes(text);
        for (int m = 0; m < merges; m++) {
            Map<Long, Integer> counts = new HashMap<>();
            for (int i = 0; i + 1 < ids.size(); i++) counts.merge(key(ids.get(i), ids.get(i + 1)), 1, Integer::sum);
            long best = -1;
            int bestCount = 0;
            for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
            }
            ByteArrayOutputStream joined = new ByteArrayOutputStream();
            joined.writeBytes(VOCAB.get((int) (best >> 32)));
            joined.writeBytes(VOCAB.get((int) best));
            RANK.put(best, m);
            VOCAB.add(joined.toByteArray());
            ids = applyMerge(ids, (int) (best >> 32), (int) best, 256 + m);
        }
    }

    static List<Integer> encode(String s) {
        List<Integer> ids = bytes(s);
        while (true) {
            int bestRank = Integer.MAX_VALUE, pos = -1;
            for (int i = 0; i + 1 < ids.size(); i++) {
                int r = RANK.getOrDefault(key(ids.get(i), ids.get(i + 1)), Integer.MAX_VALUE);
                if (r < bestRank) { bestRank = r; pos = i; }
            }
            if (pos < 0) return ids;
            ids = applyMerge(ids, ids.get(pos), ids.get(pos + 1), 256 + bestRank);
        }
    }

    static String decode(List<Integer> ids) {
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        for (int id : ids) out.writeBytes(VOCAB.get(id));
        return new String(out.toByteArray(), StandardCharsets.UTF_8);
    }

    public static void main(String[] args) {
        train("the cat sat on the mat. the dog sat on the log. public static void main(String[] args) {}", 60);
        String[] pool = {"the", " cat", " dog", "public ", "static", "\n", "\t", "    ", "é", "é", "日本", "😀", "👨‍💻", "{", "}", "0", "9", " "};
        Random rnd = new Random(2026);
        int failures = 0;
        long byteCount = 0, tokenCount = 0;
        for (int t = 0; t < 2000; t++) {
            StringBuilder sb = new StringBuilder();
            int parts = rnd.nextInt(12);
            for (int i = 0; i < parts; i++) sb.append(pool[rnd.nextInt(pool.length)]);
            String s = sb.toString();
            List<Integer> ids = encode(s);
            if (!decode(ids).equals(s)) failures++;
            byteCount += s.getBytes(StandardCharsets.UTF_8).length;
            tokenCount += ids.size();
        }
        System.out.println("vocabulary size = " + VOCAB.size());
        System.out.println("strings tested = 2000, failures = " + failures);
        System.out.println(String.format("bytes per token = %.2f", (double) byteCount / tokenCount));
        System.out.println("empty string -> " + encode("") + " -> \"" + decode(encode("")) + "\"");
    }
}
Output
vocabulary size = 316
strings tested = 2000, failures = 0
bytes per token = 1.23
empty string -> [] -> ""

All 2,000 strings survive the round trip. The pool included combining accents, Chinese and Japanese text, an emoji, a multi-code-point emoji (a person plus a laptop, joined by a zero-width joiner), tabs, and newlines.

The empty string encodes to an empty list and decodes to an empty string. This is an edge case that an encoder loop must handle without indexing past the end of the list.

The low ratio of 1.23 bytes per token is expected. This tokenizer saw only one short training text, and the test strings contain many bytes it never learned to merge. A round-trip test says nothing about quality, only about correctness.

For a vocabulary loaded from a real model, the stronger test is that the ids match a reference tokenizer. A lesson on loading a real tokenizer from GGUF, later in this course, checks this against llama-tokenize.

Example 13: SentencePiece and WordPiece markers

Every tokenizer must record where a word starts, because Hello at the start of text and Hello after a space are different. Three conventions exist, and each uses a different visible marker:

Family Marker Example for Hello world
Byte-level BPE (GPT-2, Llama 3, Qwen2) Ġ stands for the space byte, attached to the start of the word after it Hello, Ġworld
SentencePiece (Llama 2) ▁ (U+2581) replaces every space, and one is added at the start of the text ▁Hello, ▁world
WordPiece (BERT) ## marks a piece that continues a word hello, world; un, ##happi, ##ness

SentencePiece works on text characters and not on bytes. Its vocabulary has rare characters as separate entries, plus optional byte-fallback tokens. WordPiece, in its original BERT form, splits text into words first, then matches pieces greedily from the longest.

One rule decides whether a space belongs to the start of a word, is a separate token, or is a marker. The program takes one logical split (a list of pieces with a flag "starts a word") and renders it in the three conventions, for two samples.

Java
import java.util.ArrayList;
import java.util.List;

public class Markers {
    record Piece(String text, boolean startsWord) {}

    static String bpe(List<Piece> pieces) {
        List<String> out = new ArrayList<>();
        boolean first = true;
        for (Piece p : pieces) {
            out.add((p.startsWord() && !first ? "Ġ" : "") + p.text());
            first = false;
        }
        return out.toString();
    }

    static String sentencePiece(List<Piece> pieces) {
        List<String> out = new ArrayList<>();
        for (Piece p : pieces) out.add((p.startsWord() ? "▁" : "") + p.text());
        return out.toString();
    }

    static String wordPiece(List<Piece> pieces) {
        List<String> out = new ArrayList<>();
        for (Piece p : pieces) out.add((p.startsWord() ? "" : "##") + p.text().toLowerCase());
        return out.toString();
    }

    public static void main(String[] args) {
        List<List<Piece>> samples = List.of(
            List.of(new Piece("Hello", true), new Piece("world", true)),
            List.of(new Piece("un", true), new Piece("happi", false), new Piece("ness", false), new Piece("token", true), new Piece("ization", false)));
        for (List<Piece> s : samples) {
            System.out.println("byte-level BPE: " + bpe(s));
            System.out.println("SentencePiece : " + sentencePiece(s));
            System.out.println("WordPiece     : " + wordPiece(s));
            System.out.println();
        }
    }
}
Output
byte-level BPE: [Hello, Ġworld]
SentencePiece : [▁Hello, ▁world]
WordPiece     : [hello, world]

byte-level BPE: [un, happi, ness, Ġtoken, ization]
SentencePiece : [▁un, happi, ness, ▁token, ization]
WordPiece     : [un, ##happi, ##ness, token, ##ization]

The three lines per sample show the same pieces with three marker styles.

  • In byte-level BPE, the second word and later words start with Ġ, and the first word has no marker.
  • In SentencePiece, every word start gets ▁, including the first word, because SentencePiece adds a space at the start of the text.
  • WordPiece writes nothing at word starts and ## on continuations. BERT-style vocabularies also lowercase the text.

The real vocabularies show the effect on the same input. The BERT split of unhappiness is un, ha, pp, iness. The Llama 2 split is unh, app, iness. The Qwen2 split, from llama-tokenize on ggml-vocab-qwen2.gguf, is un, h, appiness. Each vocabulary found different pieces, because each came from different training text and methods. None of them splits at the morpheme boundaries un, happi, ness. Learned pieces follow frequency, not grammar.

The pinned llama.cpp build has real vocabularies for all three families. Below is real output of llama-tokenize on unhappiness tokenization, which shows that the same words split differently in each vocabulary (BERT first, then Llama 2 SentencePiece).

Terminal
llama-tokenize -m ggml-vocab-bert-bge.gguf -p "unhappiness tokenization"
llama-tokenize -m ggml-vocab-llama-spm.gguf -p "unhappiness tokenization"
Output
   101 -> '[CLS]'
  4895 -> ' un'
  3270 -> 'ha'
  9397 -> 'pp'
  9961 -> 'iness'
 19204 -> ' token'
  3989 -> 'ization'
   102 -> '[SEP]'
     1 -> '<s>'
 28859 -> ' unh'
   932 -> 'app'
  3335 -> 'iness'
  5993 -> ' token'
  2133 -> 'ization'

Read the two groups in order. The first group, from BERT, starts with the special token [CLS] (101) and ends with [SEP] (102). The second group, from Llama 2, starts with <s> (id 1). Both split unhappiness into pieces that are not grammatical, and both split tokenization into token and ization.

The tool prints the ▁ marker as a space. The stored vocabulary strings, read with gguf-py, show the markers: Qwen2 id 1879 is stored as Ġworld, id 198 as Ċ (newline), and id 286 as ĠĠĠĠĠĠĠ (seven spaces). In the Llama 2 vocabulary, id 15043 is ▁Hello and id 259 is ▁▁.

In the BERT vocabulary of llama.cpp, a converter step (phantom in conversion/bert.py) removes ## from continuation pieces and puts ▁ in front of all word-start pieces. The GGUF form is therefore the reverse of the original ## form.

Example 14: Project 1, a Tokenizer class

The project combines every step of this lesson into one class:

  • Pre-tokenization (Example 6).
  • Training on chunk counts (Example 7).
  • Encoding by merge rank, with a cache per chunk (Examples 4 and 10).
  • Special tokens split out before BPE, with a switch for user text (Example 9 and lesson 6).
  • Decoding through bytes (Example 5).
  • A token counter.
  • A text file format (Example 11).

The main method trains on a short corpus of English and Java, prints the result of each feature, and runs a round-trip test. A real tokenizer would train on much more text and use a larger vocabulary, and the class would not change.

Java
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Tokenizer {
    private static final Pattern PRE = Pattern.compile("'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+");
    private final List<int[]> merges = new ArrayList<>();
    private final Map<Long, Integer> rank = new HashMap<>();
    private final List<byte[]> vocab = new ArrayList<>();
    private final Map<String, Integer> specials = new LinkedHashMap<>();
    private final Map<String, List<Integer>> cache = new HashMap<>();

    private Tokenizer() { for (int i = 0; i < 256; i++) vocab.add(new byte[] {(byte) i}); }

    private static long key(int a, int b) { return ((long) a << 32) | b; }

    private void addMerge(int left, int right) {
        ByteArrayOutputStream joined = new ByteArrayOutputStream();
        joined.writeBytes(vocab.get(left));
        joined.writeBytes(vocab.get(right));
        rank.put(key(left, right), merges.size());
        merges.add(new int[] {left, right});
        vocab.add(joined.toByteArray());
    }

    private void addSpecials(List<String> names) {
        for (String name : names) {
            specials.put(name, vocab.size());
            vocab.add(name.getBytes(StandardCharsets.UTF_8));
        }
    }

    public static Tokenizer train(String corpus, int vocabSize, List<String> specialTokens) {
        Tokenizer t = new Tokenizer();
        Map<String, Integer> chunkCounts = new TreeMap<>();
        Matcher m = PRE.matcher(corpus);
        while (m.find()) chunkCounts.merge(m.group(), 1, Integer::sum);
        List<List<Integer>> words = new ArrayList<>();
        List<Integer> weights = new ArrayList<>();
        chunkCounts.forEach((chunk, n) -> { words.add(bytes(chunk)); weights.add(n); });
        while (256 + t.merges.size() + specialTokens.size() < vocabSize) {
            Map<Long, Integer> counts = new HashMap<>();
            for (int k = 0; k < words.size(); k++) {
                List<Integer> w = words.get(k);
                for (int i = 0; i + 1 < w.size(); i++) counts.merge(key(w.get(i), w.get(i + 1)), weights.get(k), Integer::sum);
            }
            long best = -1;
            int bestCount = 0;
            for (Map.Entry<Long, Integer> e : counts.entrySet()) {
                if (e.getValue() > bestCount || (e.getValue() == bestCount && e.getKey() < best)) { best = e.getKey(); bestCount = e.getValue(); }
            }
            if (bestCount < 2) break;
            t.addMerge((int) (best >> 32), (int) best);
            for (int k = 0; k < words.size(); k++) words.set(k, applyMerge(words.get(k), (int) (best >> 32), (int) best, t.vocab.size() - 1));
        }
        t.addSpecials(specialTokens);
        return t;
    }

    private static List<Integer> bytes(String s) {
        List<Integer> ids = new ArrayList<>();
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) ids.add(b & 0xFF);
        return ids;
    }

    private static List<Integer> applyMerge(List<Integer> ids, int left, int right, int newId) {
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < ids.size(); i++) {
            if (i + 1 < ids.size() && ids.get(i) == left && ids.get(i + 1) == right) { out.add(newId); i++; } else out.add(ids.get(i));
        }
        return out;
    }

    private List<Integer> encodeChunk(String chunk) {
        List<Integer> ids = bytes(chunk);
        while (true) {
            int bestRank = Integer.MAX_VALUE, pos = -1;
            for (int i = 0; i + 1 < ids.size(); i++) {
                int r = rank.getOrDefault(key(ids.get(i), ids.get(i + 1)), Integer.MAX_VALUE);
                if (r < bestRank) { bestRank = r; pos = i; }
            }
            if (pos < 0) return ids;
            ids = applyMerge(ids, ids.get(pos), ids.get(pos + 1), 256 + bestRank);
        }
    }

    private void encodeText(String text, List<Integer> out) {
        Matcher m = PRE.matcher(text);
        while (m.find()) out.addAll(cache.computeIfAbsent(m.group(), this::encodeChunk));
    }

    public List<Integer> encode(String text, boolean parseSpecial) {
        List<Integer> out = new ArrayList<>();
        int pos = 0;
        while (pos < text.length()) {
            int hit = -1;
            String hitName = null;
            if (parseSpecial) {
                for (String name : specials.keySet()) {
                    int at = text.indexOf(name, pos);
                    if (at >= 0 && (hit < 0 || at < hit || (at == hit && name.length() > hitName.length()))) { hit = at; hitName = name; }
                }
            }
            if (hit < 0) { encodeText(text.substring(pos), out); break; }
            encodeText(text.substring(pos, hit), out);
            out.add(specials.get(hitName));
            pos = hit + hitName.length();
        }
        return out;
    }

    public int count(String text) { return encode(text, false).size(); }

    public String decode(List<Integer> ids) {
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        for (int id : ids) out.writeBytes(vocab.get(id));
        return new String(out.toByteArray(), StandardCharsets.UTF_8);
    }

    public int vocabSize() { return vocab.size(); }

    public String piece(int id) { return new String(vocab.get(id), StandardCharsets.UTF_8).replace(' ', '_').replace("\n", "\\n"); }

    public void save(Path file) throws IOException {
        List<String> lines = new ArrayList<>(List.of("#bpe v1"));
        specials.keySet().forEach(s -> lines.add("special " + s));
        merges.forEach(mg -> lines.add(mg[0] + " " + mg[1]));
        Files.write(file, lines);
    }

    public static Tokenizer load(Path file) throws IOException {
        List<String> lines = Files.readAllLines(file);
        if (!lines.get(0).equals("#bpe v1")) throw new IOException("unknown format: " + lines.get(0));
        Tokenizer t = new Tokenizer();
        List<String> names = new ArrayList<>();
        for (String line : lines.subList(1, lines.size())) {
            if (line.startsWith("special ")) names.add(line.substring(8));
            else { String[] p = line.split(" "); t.addMerge(Integer.parseInt(p[0]), Integer.parseInt(p[1])); }
        }
        t.addSpecials(names);
        return t;
    }

    public static void main(String[] args) throws IOException {
        String corpus = """
            public class Greeter {
                private final String name;
                public Greeter(String name) { this.name = name; }
                public String greet() { return "Hello, " + name + "!"; }
                public static void main(String[] args) {
                    Greeter greeter = new Greeter("world");
                    System.out.println(greeter.greet());
                }
            }
            The greeter prints a greeting. The class has a name and a method. The method returns the greeting.
            """.repeat(3);
        Tokenizer t = Tokenizer.train(corpus, 340, List.of("<|endoftext|>", "<|im_end|>"));
        System.out.println("vocabulary size = " + t.vocabSize());
        for (int id = 256; id < 264; id++) System.out.println("id " + id + " = [" + t.piece(id) + "]");

        String sample = "public String greet() { return \"Hello, \" + name; }";
        List<Integer> ids = t.encode(sample, true);
        System.out.println("tokens = " + ids.size() + " for " + sample.length() + " characters");
        System.out.println("decoded equal = " + t.decode(ids).equals(sample));

        String chat = "Hello<|im_end|>";
        System.out.println("parse special -> " + t.encode(chat, true) + ", plain -> " + t.encode(chat, false).size() + " tokens");
        System.out.println("count(\"The greeter prints a greeting.\") = " + t.count("The greeter prints a greeting."));

        Path file = Files.createTempFile("tokenizer", ".txt");
        try {
            t.save(file);
            Tokenizer loaded = Tokenizer.load(file);
            System.out.println("loaded vocabulary size = " + loaded.vocabSize() + ", same ids = " + loaded.encode(sample, true).equals(ids));
        } finally {
            Files.deleteIfExists(file);
        }

        String[] tests = {"", " ", "\n\n", "caf\u00e9 \u65e5\u672c \uD83D\uDE00", "x = 12345;\n    return x;", "<|endoftext|>", "tabs\tand  spaces"};
        int bad = 0;
        for (String s : tests) if (!t.decode(t.encode(s, false)).equals(s)) bad++;
        System.out.println("round-trip failures = " + bad + " of " + tests.length);
    }
}
Output
vocabulary size = 340
id 256 = [__]
id 257 = [et]
id 258 = [eet]
id 259 = [reet]
id 260 = [in]
id 261 = [\n__]
id 262 = [er]
id 263 = [greet]
tokens = 18 for 50 characters
decoded equal = true
parse special -> [328, 108, 108, 111, 339], plain -> 14 tokens
count("The greeter prints a greeting.") = 8
loaded vocabulary size = 340, same ids = true
round-trip failures = 0 of 7

The vocabulary has 340 entries: 256 bytes, 82 merges, and 2 special tokens. The first learned tokens come from the corpus: two spaces (__, half of the 4-space indentation), et, eet, reet (from greet), in, newline plus indentation, er, and greet.

The Java sample of 50 characters encodes to 18 tokens, about 2.8 characters per token. This would improve with a larger corpus. With parsing on, Hello<|im_end|> becomes 5 ids that end with the special id 339. With parsing off, the same text is 14 ordinary tokens.

The save and load cycle reproduces the same ids. The seven round-trip tests pass, including the empty string, whitespace-only strings, mixed scripts, and the special-token string encoded as plain text. These behaviors, plus a pre-tokenizer pattern that matches the model, are what a tokenizer implementation has to get right.

The Tokenizer is a pure Java version of what a lesson later in this course loads from a GGUF file. The training step here uses a short corpus. For a real vocabulary, the same code needs a large text, a pre-tokenizer pattern from Example 6 that matches the target model, and a faster pair-counting loop. That later lesson reads the merges, token types, and pre-tokenizer name of a real model from its GGUF metadata and checks its output against llama-tokenize.

Interview points

  • BPE training starts from the 256 byte values, counts every neighboring pair, merges the most frequent pair into a new id, and repeats until the vocabulary reaches the target size.
  • Encoding applies the learned merges by rank: among the pairs present in a chunk, the pair that was learned first is merged first. Frequency in the input text plays no part at encode time.
  • Byte-level BPE never produces an unknown token, because any string is a sequence of bytes and every byte has an id.
  • Pre-tokenization with a regular expression splits text into chunks (words, numbers, spaces, punctuation) so that merges never cross those boundaries. The pattern is part of the tokenizer and must match the model.
  • The GPT-2 byte-to-unicode map gives every byte a printable character so merge files can be stored as text. Ġ is the visible stand-in for the space byte.
  • Special tokens are cut out of the text before BPE when parsing is on. With parsing off, the same characters encode as ordinary tokens, which prevents users from injecting control tokens.
  • Naive encoding rescans the chunk after each merge, which is about n * n work for n tokens. A priority queue of candidate pairs reduces the work for long chunks.
  • A round-trip test (decode(encode(s)) == s) over empty, whitespace-only, multi-script, and emoji strings catches most tokenizer bugs.
  • SentencePiece marks word starts with ▁, WordPiece marks continuations with ##, and byte-level BPE attaches Ġ to the start of the word after a space.

Summary

  • A BPE vocabulary is 256 byte tokens plus one token per learned merge, plus special tokens.
  • Training repeats three steps: count neighboring pairs, merge the most frequent pair, and record the merge with its rank.
  • Encoding merges pairs in rank order. Decoding concatenates the bytes of each id and decodes UTF-8 once at the end.
  • Pre-tokenization regexes keep merges inside words and differ between model families.
  • Training on chunk counts instead of the full text gives the same merges with much less work.
  • The byte-to-unicode map is why vocabulary files show Ġ for a leading space and Ċ for a newline.
  • Special tokens are matched before BPE and only when special-token parsing is enabled.
  • A priority-queue encoder does fewer operations than rescanning on long chunks and produces the same ids.
  • Saving the vocabulary and merge list is enough to rebuild an identical tokenizer.
  • The Project 1 Tokenizer class trains, encodes, decodes, handles special tokens, and passes round-trip tests. A later lesson loads a real model's tokenizer from GGUF metadata.