Build your own GPT project (TypeScript) · Chapter 2 of 12
A tokenizer: characters, then BPE
By the end of this chapter you can turn any note into a list of numbers and back, you have taught a tokenizer ChotaGPT's own vocabulary of 256 tokens from the notes, and you can say why every GPT uses tokens like these instead of single characters or whole words. Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.
- Part: Text to numbers
- 3 tasks
- TypeScript
- Free chapter
Free with a Google or GitHub sign-in, like the first 2 chapters of every lab.
Why you need this
A model does arithmetic. It multiplies and adds numbers; it cannot multiply the letter K. So before ChotaGPT can learn anything from Datta's notes, every note has to become a list of whole numbers, one for each piece of text, and every list the model writes has to become text again. The code that does both is a tokenizer, and each piece is a token.
Chapter 1 used one character as a token. That works, but it is wasteful. Here is one show note, 67 characters long:
Kal ka show (Fri 6 Nov), Kala Talkies: Ghar Wapsi Express, 9:30 pm.
In characters it is 67 tokens. ChotaGPT will read windows of 64 tokens, so a window of characters holds less than this one line. In ChotaGPT's real tokens the same line is 32 tokens, and across the training text a token is 2.04 characters: a window of 64 tokens sees about 130 characters. The model sees more of the note for the same work.
Sayali asks the plain question: "Why not one number per word, then?" Nikhil answers with this chapter: you build both kinds, a character tokenizer and a BPE tokenizer, and measure.
The lesson
Tour of the codebase
New or changed since chapter 1:
src/gpt/tokenizer.ts yours: CharTokenizer.encode and decode, pairCounts,
merge, trainBpe, BpeTokenizer.encodeChunk (the rest is given)
src/modules/tokens/tokens.routes.ts POST /tokenize, GET /tokenizer
src/state.ts now also loads the two tokenizers, once
src/app.ts adds the tokens router
scripts/make-tokenizer.ts npm run tokenizer: runs trainBpe, writes the file below
data/tokenizer.json ChotaGPT's tokenizer: 65 characters and 191 merges
src/gpt/data.ts is Nikhil's finished chapter 1. Start the API with npm run dev and send "The same note in characters". Before you write anything it answers 500, and the terminal says which task is missing:
Error: Task 1: CharTokenizer.encode is not written yet
at CharTokenizer.encode (/workspace/chapters/02-tokenizers/src/gpt/tokenizer.ts:92:11)
at <anonymous> (/workspace/chapters/02-tokenizers/src/modules/tokens/tokens.routes.ts:14:19)
...
"Tokenize a note (BPE)" stops at Error: Task 3: encodeChunk is not written yet instead. "The tokenizer's merges" already works: it only reads data/tokenizer.json, which Nikhil's finished code wrote.
One id per character
The simplest tokenizer lists every distinct character of the text, sorted, and a character's id is its place in that list. The list is the vocabulary. The constructor of CharTokenizer is given; on a tiny text:
const tok = new CharTokenizer('chai');
console.log(tok.chars, tok.stoi);
[ '?', 'a', 'c', 'h', 'i' ] Map(5) { '?' => 0, 'a' => 1, 'c' => 2, 'h' => 3, 'i' => 4 }
stoi ("string to int") is a Map from a character to its id; going back, an id is simply a place in chars. Notice the ?: it is always added. It is the unknown token, for a character the tokenizer has never seen. A Map answers undefined for a key it does not have, and ?? swaps undefined for a value you choose:
> const prices = new Map([['chai', 15], ['samosa', 20]])
> prices.get('chai')
15
> prices.get('pizza')
undefined
> prices.get('pizza') ?? 0
0
To walk the characters of a string, spread it: [...text] is an array of its characters, ready for map. Decoding is the lookup the other way, then one join, so the answer is a string.
Parda's notes use 66 distinct characters, ? among them (members ask questions), so the character tokenizer has 66 tokens. The finished "The same note in characters" answers one id for each of the 67 characters:
{"tokenizer":"char","characters":67,"tokens":67,"ids":[29,41,52,1,51,41,1,58,...],
"pieces":["K","a","l"," ","k","a"," ","s",...],"decoded":"Kal ka show (Fri 6 Nov), ..."}
Byte pair encoding: glue the most common pair
Byte pair encoding (BPE) starts from those characters and learns bigger tokens from the text itself. The rule is short:
- Count every pair of neighbouring tokens in the text.
- The most common pair becomes one new token, with the next free id.
- Replace that pair everywhere, and go back to 1.
Each new token is a merge. Stop when the vocabulary (characters plus merges) reaches the size you asked for.
First the text is cut into chunks: a word with the space before it, a number, punctuation, a space, a newline. Merges never cross a chunk's edge, so a token never glues the end of one word to the start of the next. chunks is given:
console.log(chunks('Kal ka show (Sat 2 Nov), Kala Talkies: 9:30 pm.'));
[
'Kal', ' ka',
' show', ' (',
'Sat', ' 2',
' Nov', '),',
' Kala', ' Talkies',
':', ' 9',
':', '30',
' pm', '.'
]
The pairs of neighbours in a chunk are its items 0 and 1, 1 and 2, and so on: chai has c h, h a and a i. On the text chai chai chaat, c h and h a each appear 3 times. The finished trainBpe learns five merges up to 12 tokens:
const { chars, merges } = trainBpe('chai chai chaat', 12);
console.log(chars, merges, new BpeTokenizer(chars, merges).pieces.slice(chars.length));
[
' ', '?', 'a',
'c', 'h', 'i',
't'
] [ [ 3, 4 ], [ 7, 2 ], [ 0, 8 ], [ 2, 6 ], [ 8, 5 ] ] [ 'ch', 'cha', ' cha', 'at', 'chai' ]
Read the merges as ids: [3, 4] is c then h, and it becomes token 7; [7, 2] is token 7 then a, which makes cha. Later merges are built from earlier ones.
Pairs as Map keys
Counting pairs needs a Map from a pair to its count, and here TypeScript has a trap that Python does not. A Map compares keys the way === does, and two arrays are never ===, even with the same numbers inside:
> const m = new Map()
> m.set([1, 2], 5)
Map(1) { [ 1, 2 ] => 5 }
> m.get([1, 2])
undefined
> m.set(`${1},${2}`, 5)
Map(2) { [ 1, 2 ] => 5, '1,2' => 5 }
> m.get('1,2')
5
So a pair becomes a string: pairKey(a, b) (given) makes "1,2". To get the numbers back, key.split(',').map(Number).
Ties. In round 1 of chai chai chaat, c h and h a both appear 3 times. The rule: the smaller pair wins, comparing the first ids, then the second ([3, 4] beats [4, 2]). Without a fixed rule two runs could learn different tokens, and saved weights would mean different things. Compare the numbers, never the keys: strings compare character by character, so
> '10,11' < '3,4'
true
Count over chunks, not over the text. The training text has 40,052 chunks but only 559 distinct ones: pm alone appears 1,103 times and show 812 times. Count each distinct chunk once, as an array of ids, and add its pairs as many times as it appears. words is exactly that: an array of [ids, n].
Merging never overlaps. Replacing the pair a a in a a a gives the new token followed by a: two tokens, not the new token twice. Walk left to right, and after a replacement step past both items of the pair.
The finished code, run with the given script:
$ npm run tokenizer
65 characters + 191 merges = 256 tokens, learned in 0.1 s
the training text: 149,213 characters, 73,319 tokens (2.04 characters a token)
the first merges: "al", " s", " k", "in", "ha", "ho", "at", " p"
wrote /workspace/chapters/02-tokenizers/data/tokenizer.json
al comes first because of Kal, Kala, Talkies and Mahal; s is show and seats; k is ka, ke and kal. Why 65 characters and not 66? One character, !, appears only in the validation notes, and the tokenizer learns from the training text alone. "The tokenizer's merges" lists the longest tokens learned: Balcony, Talkies, minute, office. The script writes the same data/tokenizer.json that is given, so the rest of the project uses your tokenizer's exact decisions.
Encoding with the merges, in order
Training learned a list of merges in order: rank 0 first, then rank 1, and so on. Encoding a new chunk must make the same decisions in the same order, because later merges are built from the tokens earlier merges made. Start from the characters; each round, look at the neighbouring pairs that have a merge, and apply the one learned first (the lowest rank). Stop when no pair has a merge. Here is update with ChotaGPT's tokenizer, one line per round:
rank 6 [" ","u","p","d","at","e"]
rank 75 [" ","u","p","d","ate"]
rank 76 [" ","up","d","ate"]
rank 98 [" up","d","ate"]
rank 101 [" up","date"]
rank 102 [" update"]
Picking the leftmost pair that has a merge looks harmless and is wrong: update comes out as ' up', 'da', 'te', three tokens where training made one. On the whole training text the leftmost way makes 75,428 tokens instead of 73,319, and the model would see token sequences it was never trained on.
A word the notes never use still works; it falls back to smaller pieces. And a character the tokenizer never saw becomes ?. "A character it never saw":
"pieces":["H","o","use","f","ul","l","?"," P","i","z","z","a"],"decoded":"Housefull? Pizza"
The finished "Tokenize a note (BPE)" answers 32 tokens for the 67 characters:
"pieces":["Kal"," ka"," show"," (","F","ri"," 6"," N","o","v","),"," Kala"," Talkies",":",
" Ghar"," W","a","p","s","i"," E","x","p","r","es","s",","," 9",":","30"," pm","."]
Venues and common words are one token each; a rare title like Wapsi Express is spelled out in pieces.
Characters, words or BPE
Measured on Parda's notes:
- Characters: 66 tokens, nothing is ever unknown, but the validation text is 16,240 tokens long and a window of 64 sees less than a line.
- Whole words: the training text has 664 distinct words (split on spaces), and any word not among them, like
Pizza, would have no id at all. Real English needs hundreds of thousands. - BPE with 256 tokens: the validation text is 8,087 tokens, common words are one token, and a new word falls back to pieces. With 512 tokens (
npm run tokenizer -- --vocab 512) the training text is 53,329 tokens, 2.80 characters each: a bigger vocabulary means shorter texts but more numbers in the model.
GPT-2 made the same trade at a larger size: 50,257 BPE tokens.
Your turn
- Task 1, CharTokenizer.encode and decode: the trap is
this.stoi.get(ch)alone, which givesundefined(nullin JSON) for a character the tokenizer never saw, and a decode that returns the array instead of a string. - Task 2, pairCounts, merge and trainBpe: the traps are arrays as Map keys, counting a chunk's pairs once instead of
ntimes, overlapping merges (merge([1, 1, 1], [1, 1], 9)must be[9, 1]), and a tie broken by the first pair found or by comparing keys as strings. - Task 3, BpeTokenizer.encodeChunk: the trap is merging the leftmost pair instead of the lowest rank, or stopping after one round. Nikhil will ask: why do GPTs use BPE tokens instead of characters, or instead of whole words?
Start the API with npm run dev and send "Tokenize a note (BPE)", "The same note in characters", "The tokenizer's merges", "A character it never saw" and "A tokenizer that does not exist" (422). Run npm run tokenizer and check it prints 191 merges. Then press Check.
What you build: 3 tasks
Each task has tests. You write the code in the lab's editor and press Check.
- Task 1
tokenizer.ts: one id per character
In src/gpt/tokenizer.ts write CharTokenizer.encode(text): one id per character of text, from this.stoi, and the id of UNKNOWN ("?") for a character the tokenizer has never seen. Then decode(ids): the character of each id (this.chars), joined into one string.
The Check encodes "dal" and "dal Q" with new CharTokenizer("dal chawal"), decodes back, then calls POST /tokenize with "tokenizer": "char".
- Task 2
tokenizer.ts: learn the merges
In src/gpt/tokenizer.ts write pairCounts(words): words is an array of [ids, n] (a chunk's ids and how often the chunk appears); return a Map from pairKey(a, b) (a string like "1,2") to how often that pair of neighbours appears, each chunk counted n times. Then merge(ids, pair, newId): a new array with every pair, left to right and never overlapping, replaced by newId. Then trainBpe(text, vocabSize): start from new CharTokenizer(text); words are the distinct chunks (chunks(text)) as char ids, with their counts; while characters plus merges are fewer than vocabSize, take the most common pair (a tie: the smaller pair, by its first id, then its second), give it the id chars + merges so far, add it to merges and merge it in every word; stop early if no pair is left. Return { chars, merges }.
The Check tries pairCounts and merge on small arrays, trainBpe on "aaab aaab" up to 6 tokens and on "hijk abcdefg" (every round a tie) up to 18, then on 20,000 characters of the notes.
- Task 3 · interview question
Interview: tokenizer.ts, encode with the merges
In src/gpt/tokenizer.ts write BpeTokenizer.encodeChunk(chunk): the chunk's characters as ids (the id of UNKNOWN for a character it has never seen), then rounds of merging until none applies: each round, among the neighbouring pairs that have a merge (this.ranks, keyed by pairKey), apply the one learned first (the lowest rank) everywhere, as the id this.base + its rank. Return an array of ids.
The Check encodes with hand-made tokenizers (merges bc then ab on "abc"; aa then aaaa on "aaaaa"; an unknown character), then a note with ChotaGPT's own tokenizer, then calls POST /tokenize.
Nikhil will ask: why do GPTs use BPE tokens instead of characters, or instead of whole words?
What you will learn
- Text to numbers: what a vocabulary is, and why the model only ever sees ids.
- A character tokenizer: one id per character, and what to do with a character it has never seen.
- Byte pair encoding (BPE): learn new tokens by gluing the most common pair of neighbours, again and again.
- Pairs as Map keys: why [1, 2] cannot be a key, and why "10,11" sorts before "3,4".
- Why ties and order matter: two runs must learn the same tokens, and encoding must repeat training's order.
- Characters, words or BPE: the trade, in Parda's numbers.
More in Text to numbers
Build "A tokenizer: characters, then BPE" yourself
Parda wants its team to know what a GPT really does inside. You build ChotaGPT from scratch and teach it to write Parda's Hinglish show notes. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.
Free with a Google or GitHub sign-in, like the first 2 chapters of every lab.