Subword Tokenization Algorithms

Overview

Subword tokenization algorithms decompose text into units smaller than words but larger than characters, enabling language models to handle open vocabularies efficiently. Three dominant algorithms — Byte Pair Encoding (BPE), WordPiece, and Unigram — each use different strategies for vocabulary construction and inference, but all produce subword vocabularies that capture morphological features like common roots, prefixes, and suffixes.

Byte Pair Encoding (BPE)

BPE is an additive algorithm that starts with a base vocabulary of characters and iteratively merges the most frequent adjacent pairs into new tokens until reaching a target vocabulary size.

Training process:

1. Pre-tokenize corpus into words with frequency counts
2. Initialize vocabulary with all individual characters
3. Count all adjacent token pairs across the corpus
4. Merge the most frequent pair into a single new token
5. Repeat until vocabulary reaches target size

Inference: Split input into base characters, then apply learned merge rules in the order they were created.

BPE effectively captures morphological features — common roots like “hug” and grammatical endings like “ing” emerge naturally from frequency-based merging. Used by GPT-2, GPT-3, and RoBERTa.

WordPiece

WordPiece (developed by Google, used by BERT) differs from BPE in its merge criterion and inference strategy.

Merge criterion: Instead of raw pair frequency, WordPiece uses a likelihood-based score: pair_frequency / (token_a_frequency * token_b_frequency). This penalizes frequent tokens that appear together by chance, favoring merges where tokens co-occur more than expected.

Notation: Non-starting subword units are prefixed with ## (e.g., “playing” becomes “play” + “##ing”).

Inference: Uses a greedy longest-match-first approach — scans for the largest available vocabulary unit starting from the beginning of each word.

Unigram Language Model

Unigram is a subtractive algorithm that starts with a large vocabulary and iteratively prunes tokens with the least impact on corpus loss.

Training process:

1. Initialize with an exhaustive vocabulary (all substrings up to a length limit)
2. Estimate token probabilities using Expectation-Maximization under a token independence assumption
3. Compute the loss increase from removing each token
4. Remove tokens with the smallest loss impact (retaining all base characters for universal coverage)
5. Repeat until vocabulary reaches target size

Inference: Uses the Viterbi algorithm to efficiently find the highest-probability segmentation of input text.

Used by SentencePiece (T5, ALBERT, XLNet).

Comparison

Feature	BPE	WordPiece	Unigram
Direction	Additive (merge up)	Additive (merge up)	Subtractive (prune down)
Merge criterion	Frequency	Likelihood ratio	Loss impact
Inference	Apply merges in order	Longest match first	Viterbi (max probability)
Subword marker	None (implicit)	## prefix	None (probabilistic)
Used by	GPT-2, RoBERTa	BERT	T5, ALBERT

See Also

• neural-language-modeling-transformers - Transformer architectures that consume tokenized input
• applied-machine-learning-frameworks - Hugging Face ecosystem where tokenizers are implemented
• nlp-evaluation-metrics - Metrics for evaluating models built on tokenized data