Tokenization

What tokenization is

A language model never sees a sentence as a stream of characters. It sees a sequence of pieces called tokens, each mapped to an integer id. Tokenization is that cutting step: take a piece of text, split it into tokens, look up their numbers. A token can be a whole word, a fragment of a word, a single character, or even a byte. The choice of unit matters, because it decides what the model is able to see. Coarse units leave rare words unrepresentable; very fine units turn one sentence into a long, expensive sequence.

How it works: byte pair encoding

The most widely used tokenizers today are built on byte pair encoding, or BPE. In its original form BPE is a data-compression algorithm: it takes a string and encodes it into a shorter string using a translation table^[1]. The procedure is a loop. Start from a sequence of bytes, or tokens. Count adjacent pairs. Take the most frequent pair and replace it everywhere with a new, unused token, recording that merge in a lookup table. Repeat until the vocabulary reaches the target size^[1]. Decoding runs the table backwards, undoing the merges in the opposite order until the original string comes back^[1].

A made-up example: suppose the pair "es" is the most frequent adjacent pair in a corpus. It becomes a new token, and every place where "e" was followed by "s" is rewritten as "es". In the next round the most frequent pair may be "est", which becomes another token. Common strings gradually win their own tokens, while rare strings stay as several small pieces the model already knows.

In language models the algorithm is deliberately repurposed. A modified BPE is used not to compress as hard as possible but to produce a workable set of tokens^[1]. A further variant, byte-level BPE, first converts text into a UTF-8 byte stream, so that any text at all can be encoded^[1].

Where it came from

Philip Gage first described BPE in 1994, in "A New Algorithm for Data Compression"^[1]. For years it stayed a compression technique, until Sennrich, Birch and Haddow brought it into neural machine translation in 2015 in "Neural Machine Translation of Rare Words with Subword Units"^[1]. That paper, first submitted in August 2015, attacked the open-vocabulary problem: a translation system carries a fixed word list, and anything outside it collapses into an unknown token. Their answer was to encode rare and unknown words as sequences of subword units^[2]. They compared several segmentation techniques, including character n-gram models and segmentation based on the BPE compression algorithm^[2]. The subword models beat a back-off dictionary baseline by 1.1 BLEU on the WMT 15 English-German task and by 1.3 BLEU on English-Russian^[2].

Where it is used today

Byte-level BPE is the scheme used by GPT-2, and by BERT-style models including RoBERTa, BART and DeBERTa^[1]. GPT-3.5 and GPT-4 have a vocabulary of 100,258 tokens^[1]. The practical payoff is coverage: subword tokenization lets a model represent a rare or unseen word as a sequence of smaller units instead of an unknown token, so a word missing from training data is still not a blank^[1].

Limits

The limits come from the design. Vocabulary size is a trade-off: a larger target vocabulary gives more whole strings their own token and leaves shorter fragments to be split, while a smaller one turns the same sentence into a longer token sequence^[1]. The merge table is learned by counting, so which strings end up with their own tokens depends on what the corpus contained^[1]. And tokenization is a separate step before the model: wherever the text is cut is where the model starts, and the model cannot look inside a token to see its parts. Because decoding peels the merges off one by one in reverse, encoding followed by decoding returns text that could be encoded; the byte-level scheme is what makes any text encodable in the first place^[1].