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 -The tokenizer sits between text and the model, in both directions.
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.
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 -BPE training: frequent pairs become new symbols, one merge at a time.
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());
}
}
}
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.
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 -| Tokenizer | How it differs | Used by |
|---|---|---|
| Byte-level BPE | Runs BPE on the bytes of UTF-8 text, so its 256 starting symbols cover every possible text, in any language or emoji | GPT-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 |
| WordPiece | Chooses 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) |
| SentencePiece | Works 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 model | T5, Llama 2 and many multilingual models |
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.Continue Reading: AI and LLM Papers Explained
Cosine Similarity vs Dot Product for EmbeddingsClick to read tutorial: Cosine Similarity vs Dot Product for Embeddings LLM Temperature, Top-k and Top-p Sampling ExplainedClick to read tutorial: LLM Temperature, Top-k and Top-p Sampling Explained Attention Is All You Need: The Transformer Paper ExplainedClick to read tutorial: Attention Is All You Need: The Transformer Paper Explained BERT Paper Explained: Bidirectional TransformersClick to read tutorial: BERT Paper Explained: Bidirectional Transformers Scaling Laws for Language Models (and Chinchilla) ExplainedClick to read tutorial: Scaling Laws for Language Models (and Chinchilla) Explained GPT-3 Paper Explained: Language Models Are Few-Shot LearnersClick to read tutorial: GPT-3 Paper Explained: Language Models Are Few-Shot Learners RAG Paper Explained: Retrieval-Augmented GenerationClick to read tutorial: RAG Paper Explained: Retrieval-Augmented Generation LoRA Paper Explained: Low-Rank Adaptation of LLMsClick to read tutorial: LoRA Paper Explained: Low-Rank Adaptation of LLMs Chain-of-Thought Prompting Paper ExplainedClick to read tutorial: Chain-of-Thought Prompting Paper Explained
Cosine Similarity vs Dot Product for EmbeddingsClick to read tutorial: Cosine Similarity vs Dot Product for Embeddings LLM Temperature, Top-k and Top-p Sampling ExplainedClick to read tutorial: LLM Temperature, Top-k and Top-p Sampling Explained Attention Is All You Need: The Transformer Paper ExplainedClick to read tutorial: Attention Is All You Need: The Transformer Paper Explained BERT Paper Explained: Bidirectional TransformersClick to read tutorial: BERT Paper Explained: Bidirectional Transformers Scaling Laws for Language Models (and Chinchilla) ExplainedClick to read tutorial: Scaling Laws for Language Models (and Chinchilla) Explained GPT-3 Paper Explained: Language Models Are Few-Shot LearnersClick to read tutorial: GPT-3 Paper Explained: Language Models Are Few-Shot Learners RAG Paper Explained: Retrieval-Augmented GenerationClick to read tutorial: RAG Paper Explained: Retrieval-Augmented Generation LoRA Paper Explained: Low-Rank Adaptation of LLMsClick to read tutorial: LoRA Paper Explained: Low-Rank Adaptation of LLMs Chain-of-Thought Prompting Paper ExplainedClick to read tutorial: Chain-of-Thought Prompting Paper Explained