Chapter 1 · Tokens — LLMs Explained

Before anything else happens, text is cut into pieces and each piece is given a number from a fixed list. The list and the cutting rule are chosen first and then frozen. Everything the model later learns is learned about those pieces.

History · five layers under one idea

The idea behind tokens is old: when you must turn text into something a machine can carry, give the common things short names. Seeing it as a stack of five layers, each built on the one below, makes the modern version easier to follow.

Year	Who	What they did	Status
1844–45	Samuel Morse and Alfred Vail	The telegraph code that sent the first long-distance message (24 May 1844). Vail extended Morse’s numeric code to letters, and, as the story is told, counted the type in a newspaper’s type cases to see which letters are common, then gave those the shortest dot-dash sequences. The first token list, in effect: frequent means short.	quoted: one history page; the type-case story not traced to Vail’s own writing
1948–51	Claude Shannon	Showed that letters are far from equally predictable. With 27 symbols (26 letters and the space) a uniform guess costs log₂ 27 = 4.75 bits per letter; the more context you use, the lower the cost. He also had people guess the next letter of real text, and put the entropy of English at roughly one bit per letter once long-range patterns count, about 75 percent redundancy.	quoted: Shannon 1951; the log is computed
1994	Philip Gage	Byte pair encoding, as a way to compress files: find the most common adjacent pair of bytes, replace it with an unused byte, repeat. His example turns ABABCABCD into XXCXCD and then XYYD. Nothing to do with language models yet.	quoted: C Users Journal, Feb 1994 example computed
2015	Sennrich, Haddow, Birch	Noticed that the same procedure builds a vocabulary of word pieces for translation, so a model can handle words it has never seen. This is the method of §2 below.	quoted: arXiv 1508.07909
2018	Kudo and Richardson	SentencePiece: a tokenizer that trains from raw sentences, with no earlier step of splitting into words, and is meant to work for any language. Its abstract reports a test on English–Japanese translation; Japanese is written without spaces between words, which is why a no-word-splitting step helps (my gloss, not the paper’s).	quoted: abstract of arXiv 1808.06226

Read upward, the layers are: short names for common things (Morse), the reason that works (Shannon), an automatic way to find the common things (Gage), using it for language (Sennrich), and doing it without assuming words or any particular language (Kudo and Richardson). Everything in §§1 to 3 is the third and fourth layers. What I have not covered: WordPiece and the unigram tokenizer, and how the byte-level variants used in some current models work. I did not read those sources, so they are not described here.

§1 · Three ways to cut

The simplest cut is one piece per character: the list is short (a few hundred symbols cover most scripts) but a sentence becomes a long sequence. The opposite cut is one piece per word: sequences are short, but the list must hold every word the model will ever meet, and any word it has not seen has no number. Subword tokenization sits between them: frequent words get a single number, rare words are spelled from smaller pieces, and nothing is ever unknown.

Length matters because of the cost of attention, covered in chapter 4. The transformer paper’s Table 1 gives the work of one self-attention layer as proportional to n²·d, where n is the sequence length and d the width of the representation. quoted: Vaswani et al. 2017, §4, Table 1 Halve the number of tokens and one layer does a quarter of that part of the work.

§2 · Byte pair encoding

The method the field adopted for this comes from Sennrich, Haddow and Birch (2015), who used it for machine translation. As they describe it (§3.2), the procedure is:

Write every word in the training text as its characters followed by an end-of-word mark (</w> below; the paper uses a dot), and keep a count of how often each word occurs.
Count how often each pair of neighbouring symbols occurs, weighted by word counts. Pairs never cross a word boundary.
Replace every occurrence of the most frequent pair with one new symbol, and record the merge.
Repeat. The size of the final list is the starting characters plus the number of merges, and the number of merges is the method’s single setting.
To tokenize new text, split each word into characters and apply the recorded merges in the order they were learned.

quoted: Sennrich et al. 2015, §3.2 In the text I fetched I did not find a rule for breaking ties between equally frequent pairs (the fetch was a machine summary, not a page-by-page read); my script breaks them by taking the alphabetically smallest pair, so the merge order below depends on that rule.

§3 · A worked example, computed

The toy text is four words with counts: low × 5, lower × 2, newest × 6, widest × 3, the dictionary in the paper’s own code listing. The text I fetched did not print the merges that listing would make, so I ran it. The starting list has 11 symbols (</w>, d, e, i, l, n, o, r, s, t, w). After 10 merges it has 21.

Step	Pair merged	New symbol	Count
1	e + s	es	9
2	es + t	est	9
3	est + </w>	est</w>	9
4	l + o	lo	7
5	lo + w	low	7
6	e + w	ew	6
7	ew + est</w>	ewest</w>	6
8	n + ewest</w>	newest</w>	6
9	low + </w>	low</w>	5
10	d + est</w>	dest</w>	3

The text holds 16 word occurrences. Before any merge they take 95 symbols; after ten merges they take 28, which is 3.39 times shorter. If that whole text were fed as one sequence, the n² term would fall by (95/28)² = 11.5 times. That last number is only an illustration on a four-word toy; a real corpus has a different ratio. computed: ch01-verify.py

Now the point of the method. Words the training text never contained still get tokenized, with no unknown symbol:

Word	Pieces after 10 merges	Count
low	low</w>	1
lower	low \| e \| r \| </w>	4
newer	n \| ew \| e \| r \| </w>	5
lowest	low \| est</w>	2

lowest and newer never appeared in the toy text. lowest comes out as the known piece low plus the known ending est</w>, which is the open-vocabulary behaviour the paper is about.

Try it: train your own Training text (words are counted) Number of merges 10 Word to tokenize

Same rules as the script (ties go to the alphabetically smallest pair). A toy: real tokenizers work on bytes or characters of enormous texts and have extra rules this page does not cover.

§4 · What this chapter does not establish

Which tokenizer a particular model uses, how many tokens it has, and how its rules treat spaces, capital letters or numbers are facts about each model, not about the method, and I have not checked any. I also have not measured how the number of tokens for the same sentence differs between languages. That question matters for the languages of Book XXV (English, Portuguese, Nepali, Tibetan): a tokenizer trained mostly on one language may cut another into many more pieces, which would make it costlier to read and write. That is a hypothesis here, not a finding. The test is straightforward: take one sentence in each language, run it through a published tokenizer, and count. It needs a tokenizer I can run, so it is left open.

§5 · What each statement is

Statement	Status
BPE procedure (steps 1 to 5); vocabulary = characters + merges; open-vocabulary motivation	quoted: Sennrich et al. §3.2
Self-attention cost per layer proportional to n²·d	quoted: Vaswani et al. §4, Table 1
The ten merges, symbol counts, segmentations of unseen words, the 95-to-28 reduction	computed (tie rule mine)
Squared-length factor on the toy text	computed; illustrative only
Token counts differ by language for the same sentence	open: not measured
Any claim about a specific model’s tokenizer	open: not made here

Sources

Sennrich, Haddow, Birch, “Neural Machine Translation of Rare Words with Subword Units”, arXiv 1508.07909 (2015) · Vaswani et al., “Attention Is All You Need”, arXiv 1706.03762 (2017). Gage, “A New Algorithm for Data Compression”, C Users Journal, Feb 1994 (archive copy) · Shannon, “Prediction and Entropy of Printed English”, 1951 (course copy) · Kudo and Richardson, SentencePiece, arXiv 1808.06226 (2018) · History of Information, entry on Morse code. Companion script: book16/ch01-verify.py.