Tokens and Tokenization

Tokens are the fundamental unit of currency in modern LLMs. Long context windows are measured in tokens, API pricing is per-token, and rate limits are often expressed in tokens per minute. But what actually is a token?

A token is a piece of a word. As a rule of thumb, one token is roughly equivalent to 4 characters or 3/4 of a word for English text. The dominant algorithm for splitting text into tokens is byte pair encoding (BPE), originally designed for data compression but repurposed in a 2016 paper for word segmentation in machine learning tasks. This article reviews BPE, provides a complete implementation in Go, and shows how to make it compatible with OpenAI's tiktoken library, producing identical results with the same vocabulary files.

How Byte Pair Encoding Works

BPE takes arbitrary text with words, numbers, whitespace and punctuation as input, and outputs a list of tokens — integer identifiers that look up to sub-word byte sequences in a vocabulary. The algorithm has a critical pre-processing step: splitting input text into words via a customizable regular expression. Different models and vocabularies use different splitter regexps. The splitter typically does some whitespace-based splitting (with whitespace preserved) to prevent inter-word tokens.

For example, a word splitter on the lyric "i'm blue da ba dee da ba daa" produces words where spaces are replaced with underscores for presentation:

i
'm
_blue
_dabadee
_dabadam
  • The contraction 'm is split from i — this is common for English splitters, which separate 'm, 'll, 're into their own words.
  • Whitespace is attached at the start of a word. This matters because tokens at the beginning of words can have different semantic meaning from tokens elsewhere. From this point on, whitespace bytes are treated like any other bytes in BPE.

Key terminology:

  • Word: produced by the splitter during pre-processing
  • Token: typically a sub-word sequence of bytes
  • Token ID: unique numerical identifier for a token
  • Vocabulary: mapping of token IDs to token values learned during training
  • Training: the process of learning a vocabulary from a text corpus
  • Splitter regexp: defines text-to-words splitting; with a given algorithm, pair of vocabulary + splitter regexp unambiguously defines tokenization
  • Encoder: tokenizes text into vocabulary IDs given a vocabulary and splitter regexp
  • Decoder: reconstructs original text from IDs and vocabulary

Training the Vocabulary

BPE training begins by assuming each byte is its own token, then iteratively merges pairs of tokens into longer ones, adding to the vocabulary until the desired size is reached. Starting with our example words:

i
'm
_blue
_dabadee
_dabadam

The process creates a token for each byte in the range [0..255], so the minimum vocabulary size is 256. Each iteration:

  • Count occurrences of each ordered pair of adjacent bytes
  • Create a new token ID mapping to the concatenation of the most common pair
  • Replace that pair with the combined token throughout the input

Having split input words into single-byte lists, we count pair frequencies:

[d a] --> 3
[a b] --> 2
[b a] --> 2
[' m] --> 1
[_ b] --> 1
[l u] --> 1
[u e] --> 1
[_ d] --> 2
[a d] --> 2
[d e] --> 1
[e e] --> 1
[b l] --> 1
[a m] --> 1

Since "da" is most common, we create a token for it and substitute it everywhere:

[i]
[' m]
[_ b l u e]
[_ da b a d e e]
[_ da b a da m]

Repeating the process, we count pairs again in the new working list:

[e e] --> 1
[a da] --> 1
[l u] --> 1
[_ da] --> 2
[da b] --> 2
[a d] --> 1
[d e] --> 1
[da m] --> 1
[' m] --> 1
[_ b] --> 1
[b l] --> 1
[u e] --> 1
[b a] --> 2

Several pairs have equal counts; picking arbitrarily, say _da (space followed by "da"), we add it as a token and substitute:

[i]
[' m]
[_ b l u e]
[_da b a d e e]
[_da b a da m]

The process stops when either no pairs remain (each word is one token), or — more realistically for real corpora — when we reach our desired vocabulary size. GPT-4's vocabulary, for instance, has around 100,000 tokens. Training output is a vocabulary; after the two cycles above, we'd have 258 tokens: 256 single-byte tokens, plus da and _da, each with a unique integer ID.

Encoding Text

Encoding is what happens whenever text is fed into an LLM. The input, a splitting regexp, and a vocabulary produce a token list. For "yada daba", splitting and byte-decomposition yields:

[y a d a]
[_ d a b a]

BPE encoding applies learned tokens greedily, in the order they were learned. Assigning monotonically increasing integer IDs to new tokens makes this straightforward — lower IDs are prioritized. First, apply token da, learned first:

[y a da]
[_ da b a]

Then _da:

[y a da]
[_da b a]

With no more learned tokens to apply, the final result is 6 tokens.

Real Vocabularies and Splitting Patterns

The toy examples scale directly to production models. GPT-4's tokenizer uses the cl100k_base vocabulary — 100k tokens beyond the 256 byte tokens — the same encoding used by tiktoken. The vocabulary file is freely downloadable and base64-encoded on disk:

" Fritz"  91083
"Initially"  91084
"nodeValue"  91085
"_TRIANGLES"  91086
"-backend"  91087

Tokens are shown left with numerical IDs right. The algorithm is unsentimental about its training material — names, code fragments, whatever appears.

The companion splitting regexp contains multiple alternatives and handles space-delimited words, keeping spaces in front of words and treating English contractions as separate words, plus grouping long numbers in threes:

(?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\r\n\p{L}\p{N}]?\p{L}+|\p{N}{1,3}| ?[^\s\p{L}\p{N}]+[\r\n]*|\s*[\r\n]+|\s+(?!\S)|\s+

Go programmers take note: the pattern includes ?!, a negative lookahead that the standard regexp package doesn't support. The third-party regexp2 package implements it.

Browser Demo

The referenced Go implementation isn't just a pedagogical exercise — it reproduces OpenAI's actual tokenizer for its most modern models. The cmd/wasm directory in the repository compiles BPE to WebAssembly, loaded via JavaScript glue in a simple HTML page. The JS watches the text box and sends input to an exported Go function, which tokenizes on the fly. A selector button toggles between token strings and numerical IDs — matching tiktoken's output.

Screenshot of tokenizer with a sample text, showing tokens

[1] The vocabulary encodes a bijective mapping, so token IDs uniquely determine text.

[2] We're glossing over some details; the BPE paper has the full story.

[3] The regexp2 module backs the splitter for the demo and test cases with real vocabularies.

[4] The online demo closely mirrors OpenAI's own tokenizer page.