Tokenization Explained: Byte Pair Encoding in Java

Introduction

Before a large language model reads a single word, a tokenizer has already cut the text into tokens and turned each one into a number. The tokenizer decides what a model's prices, limits and context windows are counted in, why some languages cost more than others, and why models sometimes stumble over spelling and digits. Most modern LLMs use a variant of one algorithm, byte pair encoding (BPE). This post explains tokenization with diagrams: the path from text to token ids, how BPE learns its vocabulary - implemented and run in Java - how it splits words it has never seen, how WordPiece, SentencePiece and byte-level BPE differ, and what all this means for developers.

(Note - Why tokens matter for cost and limits is explained in LLM tokens, context windows, embeddings and hallucinationsClick to read tutorial: LLM Tokens, Context Windows, Embeddings and Hallucinations; this post shows how the tokens are made.)

From text to token ids

A model works with numbers, not text. Tokenization is the first step of every request, and its reverse is the last step of every answer -
Text is split into words and spaces, the tokenizer's merges turn each word into vocabulary pieces, each piece is looked up as a token id, and the ids select embedding vectors which the model reads Text"the lowest" Pre-tokenizesplit on spaces Apply mergesthe_ | low est_ Token ids[312, 87, 905] Embeddings3 vectors the vocabulary maps every piece to a fixed id, and every id to a learned embedding vector Generating text runs the same path backwards: the model outputs an id, the tokenizer looks up its piece, and the pieces are joined into text. The ids here are made up; every tokenizer has its own vocabulary and numbering.
The tokenizer sits between text and the model, in both directions.
The tokenizer is trained once, on a large sample of text, before the model itself is trained, and is then frozen: a model can only ever read and write the pieces of its own vocabulary. The question is how to choose those pieces.

Why not words or characters?

  • Whole words make a huge vocabulary - every form of every word, every name, every typo - and still fail on the first new word, which becomes "unknown".
  • Single characters make a tiny vocabulary which can spell anything, but sequences become several times longer, and the model has to spend its capacity learning to assemble letters into words. AttentionClick to read tutorial: Attention Is All You Need: The Transformer Paper Explained costs grow with the length of the sequence, so this is expensive.
  • Sub-words sit in between: common words are single tokens, and rare words are spelled from a few common pieces. A vocabulary of 30,000 to a few hundred thousand pieces covers any text with sequences only a little longer than the word count.
BPE is the most widely used way of choosing those sub-word pieces.

How byte pair encoding learns its vocabulary

BPE started as a data-compression technique (Gage, 1994) and was adapted for language models by Sennrich, Haddow and Birch in 2016. Training is a simple loop -
Start with every word split into characters; count every adjacent pair of symbols weighted by word frequency; merge the most frequent pair into a new symbol and add it to the vocabulary; repeat until the vocabulary has the wanted size 1. Split every wordinto charactersn e w e s t _ 2. Count adjacentpairs in the corpus"e s" seen 9 times 3. Merge the mostfrequent paire + s → es 4. Record themerge rule"es" joins the vocab repeat until the vocabulary reaches its target size (tens of thousands of merges for a real model) The output is an ordered list of merge rules; the vocabulary is the characters plus one new symbol per merge.
BPE training: frequent pairs become new symbols, one merge at a time.
Because pairs are counted over the whole corpus, weighted by how often each word occurs, the merges follow the text's statistics: frequent words become single tokens quickly, and frequent endings such as "est" or "ing" become reusable pieces. The program below implements BPE training and tokenization on the small example corpus from Sennrich et al. - "low" 5 times, "lower" twice, "newest" 6 times and "widest" 3 times - with "_" marking the end of a word.
Training byte pair encoding and tokenizing new words
//BytePairEncoding.java
import java.util.*;

public class BytePairEncoding {

  // A word as a list of symbols; "_" marks the end of a word, so "low" at the end differs from "low" inside "lower"
  static List<String> split(String word) {
    List<String> symbols = new ArrayList<>();
    for (char c : word.toCharArray()) symbols.add(String.valueOf(c));
    symbols.add("_");
    return symbols;
  }

  // Replaces every adjacent pair (a, b) in the word by the merged symbol a+b
  static List<String> merge(List<String> symbols, String a, String b) {
    List<String> out = new ArrayList<>();
    for (int i = 0; i < symbols.size(); i++) {
      if (i < symbols.size() - 1 && symbols.get(i).equals(a) && symbols.get(i + 1).equals(b)) {
        out.add(a + b);
        i++;
      } else {
        out.add(symbols.get(i));
      }
    }
    return out;
  }

  public static void main(String[] args) {
    // Training corpus: word -> how often it occurs (the example from the BPE paper, Sennrich et al. 2016)
    Map<String, Integer> corpus = new LinkedHashMap<>();
    corpus.put("low", 5);
    corpus.put("lower", 2);
    corpus.put("newest", 6);
    corpus.put("widest", 3);

    Map<String, List<String>> words = new LinkedHashMap<>();
    corpus.keySet().forEach(w -> words.put(w, split(w)));
    List<String[]> merges = new ArrayList<>();

    // Training: repeatedly merge the most frequent adjacent pair of symbols
    for (int step = 1; step <= 10; step++) {
      Map<String, Integer> pairCounts = new LinkedHashMap<>();
      for (var e : words.entrySet()) {
        List<String> s = e.getValue();
        for (int i = 0; i < s.size() - 1; i++)
          pairCounts.merge(s.get(i) + " " + s.get(i + 1), corpus.get(e.getKey()), Integer::sum);
      }
      var best = pairCounts.entrySet().stream().max(Map.Entry.comparingByValue()).get();
      String[] pair = best.getKey().split(" ");
      merges.add(pair);
      words.replaceAll((w, s) -> merge(s, pair[0], pair[1]));
      System.out.printf("merge %2d: %-4s + %-4s -> %-7s (seen %2d times)   %s%n",
          step, pair[0], pair[1], pair[0] + pair[1], best.getValue(), words.values());
    }

    // Tokenizing: apply the learned merges, in order, to any word - also words never seen in training
    System.out.println();
    for (String word : List.of("lowest", "newer", "wider", "slow")) {
      List<String> s = split(word);
      for (String[] m : merges) s = merge(s, m[0], m[1]);
      System.out.printf("%-7s -> %s (%d tokens)%n", word, s, s.size());
    }
  }
}
 OUTPUT of the above code
merge  1: e    + s    -> es      (seen  9 times)   [[l, o, w, _], [l, o, w, e, r, _], [n, e, w, es, t, _], [w, i, d, es, t, _]]
merge  2: es   + t    -> est     (seen  9 times)   [[l, o, w, _], [l, o, w, e, r, _], [n, e, w, est, _], [w, i, d, est, _]]
merge  3: est  + _    -> est_    (seen  9 times)   [[l, o, w, _], [l, o, w, e, r, _], [n, e, w, est_], [w, i, d, est_]]
merge  4: l    + o    -> lo      (seen  7 times)   [[lo, w, _], [lo, w, e, r, _], [n, e, w, est_], [w, i, d, est_]]
merge  5: lo   + w    -> low     (seen  7 times)   [[low, _], [low, e, r, _], [n, e, w, est_], [w, i, d, est_]]
merge  6: n    + e    -> ne      (seen  6 times)   [[low, _], [low, e, r, _], [ne, w, est_], [w, i, d, est_]]
merge  7: ne   + w    -> new     (seen  6 times)   [[low, _], [low, e, r, _], [new, est_], [w, i, d, est_]]
merge  8: new  + est_ -> newest_ (seen  6 times)   [[low, _], [low, e, r, _], [newest_], [w, i, d, est_]]
merge  9: low  + _    -> low_    (seen  5 times)   [[low_], [low, e, r, _], [newest_], [w, i, d, est_]]
merge 10: w    + i    -> wi      (seen  3 times)   [[low_], [low, e, r, _], [newest_], [wi, d, est_]]

lowest  -> [low, est_] (2 tokens)
newer   -> [new, e, r, _] (4 tokens)
wider   -> [wi, d, e, r, _] (5 tokens)
slow    -> [s, low_] (2 tokens)

Explanation of the code

  • The first merges were "e + s", then "es + t", then "est + _": the ending "est" occurs in "newest" (6 times) and "widest" (3 times), 9 times in all, more than any other pair. Next came "lo" and "low", from "low" and "lower" (7 times together).
  • After ten merges, "newest" and "low" are single tokens, while "widest" is still "wi + d + est_" - with more merges it would become a token too. A real tokenizer runs tens of thousands of merges over billions of words.
  • Tokenizing applies the merges in the order they were learned. "lowest" never appeared in training, yet it became just two tokens, "low" and "est_". "slow" became "s" and "low_": the unseen letter stays a token of its own, so any word can be tokenized - nothing is ever "unknown".
  • The end-of-word marker matters: "low_" is the whole word "low", while "low" without it is the start of "lower" or "lowest". Real tokenizers mark word boundaries in a similar way, for example by attaching the space to the start of the next word.
The diagram shows how the learned merges built the two tokens of "lowest" -
l and o merge into lo, lo and w into low; e and s merge into es, es and t into est, est and the end marker into est_; the result is the two tokens low and est_ lowest_ loes est lowest_ merges 4 and 5merges 1, 2 and 3 2 tokens
Tokenizing "lowest" with the merges learned from the corpus: seven characters become two tokens.

The tokenizer families

Real tokenizers refine the same idea in different ways -
TokenizerHow it differsUsed by
Byte-level BPERuns BPE on the bytes of UTF-8 text, so its 256 starting symbols cover every possible text, in any language or emojiGPT-2 and GPT-3Click to read tutorial: GPT-3 Paper Explained: Language Models Are Few-Shot Learners (50,257 tokens: 256 bytes, 50,000 merges and one end-of-text token), and most current LLMs
WordPieceChooses the merge which most increases the likelihood of the training text, rather than the most frequent pair; marks word-internal pieces with "##"BERTClick to read tutorial: BERT Paper Explained: Bidirectional Transformers (30,000 tokens)
SentencePieceWorks on raw text without splitting on spaces first, treating the space as a symbol ("▁"), so it suits languages without spaces; offers BPE or a unigram modelT5, Llama 2 and many multilingual models
Vocabulary sizes have grown over time: about 50,000 tokens for GPT-3, and from 100,000 to over 200,000 in several current model families. A larger vocabulary makes each text fewer tokens, especially for code and non-English text, at the cost of a larger embedding table.

What tokenization means for developers

  • Token counts depend on the tokenizer. The same text has different counts in different model families, so count with the tokenizer of the model you call - or read the counts the API returns.
  • Languages are not equal. Tokenizers learn from training data in which English dominates, so the same sentence in many other languages needs more tokens - and costs more, and fills the context window faster.
  • Spelling and digits are hard to see. A model sees "strawberry" as one or a few tokens, not as letters, which is why counting letters or reversing words trips models up. Numbers are often split into irregular groups of digits, which makes exact arithmetic harder.
  • Whitespace and formatting are tokens too. Indentation in code and repeated spaces cost tokens; tokenizers trained on code merge common runs of spaces to keep this cheap.
  • Special tokens - end of text, the markers between chat roles (see prompt engineering techniquesClick to read tutorial: Prompt Engineering Techniques Explained with Examples) - are part of the vocabulary as well; the API inserts them for you.

Summary

In this post we went through tokenization. We saw that a tokenizer turns text into token ids before the model reads it, and turns ids back into text after the model writes, and why sub-word tokens beat both whole words and single characters. We went through byte pair encoding, which learns its vocabulary by repeatedly merging the most frequent pair of symbols, implemented its training and tokenization in Java, and saw words it had never seen split into known pieces. Lastly, we compared byte-level BPE, WordPiece and SentencePiece, and saw what tokenization means for costs, languages, spelling and digits. In the next post, we will look at how the meaning of text is compared, in cosine similarity vs dot product for embeddingsClick to read tutorial: Cosine Similarity vs Dot Product for Embeddings.