Tokenization: BPE and SentencePiece

The algorithms, their tradeoffs, and their pitfalls.

Summary

Byte-Pair Encoding (BPE) and SentencePiece are the two tokenization algorithms behind nearly every modern LLM. BPE greedily merges frequent byte pairs; SentencePiece treats input as a raw byte stream and learns segmentation. The choice affects multilingual performance, code performance, and inference cost.

Objectives

01Describe BPE's merge procedure in three steps.
02State the practical difference between BPE and SentencePiece.
03Explain why byte-level BPE handles arbitrary text.

The Lesson

BPE, procedurally

Start with byte-level tokens. Count adjacent-pair frequencies. Merge the most frequent pair into a new token. Repeat until you hit the vocabulary size. GPT-2 and GPT-4 both use byte-level BPE.

SentencePiece

Google's tokenizer library implements BPE and Unigram Language Model tokenization. It treats whitespace as a normal character, which handles languages without word boundaries (Japanese, Chinese) uniformly. T5, PaLM, and LLaMA use SentencePiece.

The tradeoffs

Byte-level BPE handles anything, but produces long token sequences for non-Latin scripts. Learned SentencePiece vocabularies can be tuned per corpus but shift when the corpus does. Both are engineering choices, not theoretical positions.

Key Ideas

BPE merges frequent pairs; SentencePiece learns whole-corpus segmentation.
Byte-level tokenizers never fail on unseen text but cost more tokens for it.

References

Sennrich et al., 'Neural Machine Translation of Rare Words with Subword Units' (2016)

← Tokens, precisely Embeddings →