# 12. Tokens: from characters to BPE > Where does text get cut into pieces, and why does it matter? LLM by Hand · Theory · runs in your browser · interactive page: https://llm.liko.page/learn/tokenization/ Level 11's model predicted the next **word**. But "word" was a choice. A model reads a list of **tokens**, and someone has to decide where one token ends and the next begins. That choice sets the size of the vocabulary, the length of every sequence, and which texts the model can read at all. Each distinct token gets an **id**, a number from 0 up to the vocabulary size minus one. Level 13 turns ids into vectors. ## 1. Cutting into characters The simplest cut: every character is a token. Take the word `hello`. The **vocabulary** is the list of distinct characters in it, sorted alphabetically. Each character's id is its position in that list, counting from 0. Compute it before you look: **Question.** With the text “hello”, how many characters are in the vocabulary? *Answer it on the page to check your work.* **Question.** In “hello”, what is the id of “l”? *Answer it on the page to check your work.* Now check yourself in the lab, and type anything else you like. *[Interactive lab: Char token — open the page to use it]* The vocabulary gives two dictionaries: `stoi` (string to id) and `itos` (id to string). Code that builds them uses two Python tools: ```python list(enumerate(["e", "h", "l"])) # [(0, 'e'), (1, 'h'), (2, 'l')] each item with its position {c: i for i, c in enumerate(["e", "h"])} # {'e': 0, 'h': 1} a dictionary built in one line ``` That one-line form is called a dictionary comprehension. The same form with `[ ]` builds a list (a list comprehension). **Code question.** Build stoi: a dictionary from each character to its id (its position in chars). Fill in the blank (`____`): ```python chars = sorted(set("hello")) # ['e', 'h', 'l', 'o'] stoi = ____ print(stoi) ``` *Answer it on the page to check your work.* Encoding looks up every character. Decoding goes back. Nothing is lost on the way. **Code question.** Write encode: turn a string into a list of ids. Fill in the blank (`____`): ```python text = "hello" chars = sorted(set(text)) stoi = {c: i for i, c in enumerate(chars)} itos = {i: c for c, i in stoi.items()} def encode(s): return ____ def decode(ids): return "".join(itos[i] for i in ids) print(stoi) print(encode("hello"), decode(encode("hello"))) ``` *Answer it on the page to check your work.* **If you are stuck: Why sort the characters? Does it matter which character gets which id?** It doesn't matter at all. Any fixed order works, as long as encoding and decoding use the same one. Sorting is an easy way to get the same order every time you run the code. The ids are names, not amounts: “l” being 2 doesn’t make it twice “h”. Level 13 shows how the model avoids reading them as amounts. ## 2. Cutting into words Characters give a tiny vocabulary but long sequences: "hello" is 5 tokens. The other extreme is one token per word. Level 11 did that, with the vocabulary of its stories: the, a, cat, dog, sat, ran, on, mat, rug, and ".". **Predict.** A word-level tokenizer knows only: the, a, cat, dog, sat, ran, on, mat, rug, “.”. How does it encode “the cats sat .”? A. 4 tokens, but “cats” becomes an unknown token B. It finds that cats = cat + s C. 5 tokens *Answer it on the page to check your work.* Whole words have two problems. Every form of a word needs its own entry (cat, cats, catlike, …), so a real vocabulary would need millions of entries. And a word that wasn't in the list can't be read at all. ## 3. Byte-pair encoding: let the data decide **BPE** starts from characters and builds bigger tokens out of pieces that often appear together: 1. Cut every word into characters. 2. Count every pair of neighboring tokens, across all the words, weighted by how often each word appears. 3. Merge the most frequent pair into one new token. Add it to the vocabulary. 4. Repeat from step 2, as many times as you like. Here is a tiny word list: **cat** appears 4 times, **cats** 2 times, **hat** 3 times, **hats** 1 time. **Question.** Words: cat ×4, cats ×2, hat ×3, hats ×1. Cut into characters, how many times does the pair a + t appear in total (counting each word as often as it appears)? *Answer it on the page to check your work.* So the first merge is a + t → "at". Now the words are c·at, c·at·s, h·at, h·at·s. **Question.** After merging a + t, the words are c·at ×4, c·at·s ×2, h·at ×3, h·at·s ×1. How many times does the pair c + at appear now? *Answer it on the page to check your work.* That pair wins, so merge 2 is c + at → "cat". Merge 3 is h + at → "hat". With those 3 merges, a word is encoded by cutting it into characters and applying the merges **in the order they were learned**. **Question.** The merges, in order, are: 1) a + t → at, 2) c + at → cat, 3) h + at → hat. How many tokens is “cats”? *Answer it on the page to check your work.* **Question.** Same three merges (a + t → at, c + at → cat, h + at → hat). “that” was never in the word list. How many tokens is it? *Answer it on the page to check your work.* Now step through it yourself. The lab starts with the same four words. Then switch to the 40 generated words (8 base words, called stems, like *play*, *walk*, *cook* with the endings -s, -ed, -ing, -er, each with a count from a fixed rule). One question before you start merging: **Predict.** BPE runs on a list of 40 words, and you keep merging. Each merge adds one token to the vocabulary. What happens to the total number of tokens across all the words? A. It keeps shrinking B. It stays the same C. It grows with the vocabulary *Answer it on the page to check your work.* *[Interactive lab: Bpe — open the page to use it]* **Try it** With the generated words, watch the first merges: k + e, a + l, o + o, i + n, then in + g. BPE finds pieces like “ke” (from walked, cooker, …) and “ing” without being told what an ending is. Then type a word that isn't in the list, like `jumping` or `parker`, and see it split into known pieces. Applying one merge to a word is a small loop. Write the condition: **Code question.** Complete merge: replace every neighboring (a, b) in seg with the single token a + b. Fill in the blank (`____`): ```python def merge(seg, a, b): out, i = [], 0 while i < len(seg): if i + 1 < len(seg) and ____: out.append(a + b) i += 2 else: out.append(seg[i]) i += 1 return out print(merge(list("cats"), "a", "t")) ``` *Answer it on the page to check your work.* Step 2 of BPE counts the pairs. Two Python tools do it: ```python seg = ["c", "a", "t", "s"] list(zip(seg, seg[1:])) # [('c', 'a'), ('a', 't'), ('t', 's')] every neighboring pair d = {} d["x"] = d.get("x", 0) + 4 # {'x': 4} get gives 0 when the key is not there yet ``` A word that appears n times adds n to each of its pairs, as in the count of a + t above. **Code question.** Write the inside of the loop: for one word seg that appears n times, add n to the count of each of its neighboring pairs. The words are cat ×4, cats ×2, hat ×3, hats ×1. Two lines. Fill in the blank (`____`): ```python segs = [list("cat"), list("cats"), list("hat"), list("hats")] counts = [4, 2, 3, 1] def pairs(segs, counts): pc = {} for seg, n in zip(segs, counts): ____ return pc pc = pairs(segs, counts) print(pc) ``` *Answer it on the page to check your work.* ## 4. How many merges? Each merge adds one token to the vocabulary and makes the sequences shorter. On the 40 generated words: before any merge there are 19 characters and 1,068 tokens; after 40 merges, the vocabulary has 59 entries and the words take only 263 tokens. Fewer tokens means less work per text. It also means more text fits in the model's **context window**: a model reads at most a fixed number of tokens at once, so the shorter each text, the more of it the model can see. A big vocabulary also has a cost. The model keeps an **embedding table**: a plain table with one row of numbers per token (level 13 shows how it is used). Every token needs its own row there, and its own column in the final layer that scores the next token. **Question.** A vocabulary of 50,000 tokens, with 512 numbers per token in the embedding table. How many numbers does the table hold, in millions? (Answer in million.) *Answer it on the page to check your work.* **Deeper: What real tokenizers do differently** - **They start from bytes, not characters.** Every text is a list of bytes, values 0 to 255, so the starting vocabulary is 256 and nothing is ever unknown: an emoji or a rare script just becomes several byte tokens. - **Spaces stick to words.** Text is first split so that a space travels with the word after it, so "␣cat" and "cat" are different tokens. That keeps spacing exact when decoding. - **Tens of thousands of merges.** Real vocabularies have about 30,000 to 200,000 tokens. Common words become one token; rare words become two to five pieces. The idea is the same as the lab: count pairs, merge the most frequent, repeat. **If you are stuck: Why do models struggle to spell, count letters, or do arithmetic on long numbers?** Because they never see the letters. A word like "chatting" may arrive as two tokens, say "chat" and "ting". The model gets two ids, not eight characters. To count the t's, it has to have learned what is inside each token. Numbers are cut the same arbitrary way: "12345" might become "123" and "45", while "12346" is cut differently. The digits are not in the same columns from one number to the next, which makes column-by-column arithmetic hard. Some models fix this by always splitting numbers into single digits. ## You can now - Build a character vocabulary, give each character an id, and encode a string as a list of ids. - Count weighted neighboring pairs and run a few BPE merges by hand. - Encode a new word by applying the learned merges in the order they were learned.