Byte-Pair Encoding (2 blogmarks)

This article is an excellent resource for what BPE (Byte-Pair Encoding) is, what the relevant research is (and how they relate to one another), and some intuition for why BPE is a good choice when it comes to build, training, and operating LLMs.

BPE was originally proposed by Philip Gage in 1994 in A New Algorithm for Data Compression.

But how do we get from simple, unpopular compression algorithm from the 90s to BPE being foundational to LLMs?

Here is the problem:

Statistical NLP models require vocabularies, which are lists of known words. But how big should the vocabulary be?

• Too small: Common words only. "The", "a", "is" work fine. But "iPhone"? "COVID-19"? "Beyonce"? All become (unknown).
• Too large: Include every word ever written. The vocabulary explodes. English has 500,000+ dictionary words. Add proper nouns, technical terms, misspellings, and you're at millions. Each word needs an embedding vector (hundreds or thousands of parameters). Memory and computation blow up.

The field settled on an uncomfortable compromise: fixed vocabularies of 30,000-50,000 words, with everything else mapped to .

BPE was recognized as an effective way to build a vocabulary for machine learning workloads in Neural Machine Translation of Rare Words with Subword Units. I'm very curious what draw Sennrich et al.'s attention to the BPE algorithm and how it clicked as a candidate for building expressive vocabularies.

The key insight: BPE automatically identifies morpheme-like units.

Other subword tokenization techniques besides raw BPE are WordPiece and SentencePiece -- Linguistic Laws Meet Protein Sequences: A Comparative Analysis of Subword Tokenization Methods.

From the author of Build a Large Language Model (from scratch), here is a jupyter notebook that implements a basic BPE (byte-pair encoding) tokenizer for use with an LLM. Training, prompting, and responses make use of a fixed BPE tokenizers. In practice you probably want to make use of an optimized implementation like tiktoken from OpenAI. That said, it can still be informative and fun to build your own from scratch.

When I started working through the Build an LLM book, I wanted to get a better understanding of BPE, so I wrote my own tokenizer in Python.