Tokenization and Embeddings
A tokenizer turns text into ids, and an embedding table turns ids into learned vectors. Built from scratch: BPE merges, byte-level fallback, and cosine similarity on toy vectors.
Tokenization splits text into subword pieces with fixed integer ids, and an embedding table maps each id to a learned vector that the model reads. Byte pair encoding builds the vocabulary by repeatedly merging the most frequent adjacent pair. Interviewers expect the byte-level detail: starting from all 256 byte values means no string is ever unknown.
A language model reads integers, not text: a tokenizer splits the input into subword pieces with fixed ids, and an embedding table maps each id to a learned vector. Byte pair encoding learns those pieces by merging frequent pairs, and cosine similarity compares the vectors. Every number on this page comes from code you can run in a few seconds.
- Byte pair encoding builds a tokenizer vocabulary by repeatedly merging the most frequent adjacent pair of symbols, and the number of merges is the setting you choose.
- GPT-2's byte-level BPE vocabulary has 50,257 entries: 256 byte values, 50,000 learned merges and one end-of-text token.
- A character-level tokenizer emits [UNK] for any symbol it never saw in training, while byte-level BPE can encode and decode any string exactly.
- Text that was rare in a tokenizer's training data costs more tokens: in a toy byte-level tokenizer, 4 characters of Japanese with a space became 10 tokens.
- An embedding lookup reads one row of the embedding table, which is the same as multiplying a one-hot vector by the table.
- Cosine similarity is the dot product divided by both vector lengths, so for vectors normalised to length 1 it equals the dot product.
01Text to ids to vectors
A language model never sees letters. A tokenizer cuts the input into pieces called tokens, each piece becomes its integer id in a fixed vocabulary, and each id picks one row of an embedding table. That row, a list of d floating-point numbers, is what the network reads.
The diagram follows one word through those steps using the small tokenizer trained later on this page. The word " replayed", with its leading space, becomes three tokens: " replay", "e" and "d". Their ids are 271, 101 and 100. Those ids are only row numbers: nothing about 271 says the token is related to "play". The meaning lives in the rows of the embedding table, which are learned like any other weight.
Two consequences follow. First, the tokenizer and the model are a matched pair. Swap in a different tokenizer and id 271 now points at a different string, so the model reads nonsense. Second, the tokenizer is trained once, before the model, usually by a counting procedure such as BPE, while the embedding table is trained by gradient descent together with the rest of the network.
02Words, characters or subwords
Word-level tokenization splits on spaces and punctuation and gives every training word an id. The vocabulary gets enormous, because "play", "plays", "played" and "replay" are separate entries that share nothing, and any unseen word maps to one unknown token, written [UNK]. Splitting on spaces also assumes the language puts spaces between words, which Chinese and Japanese do not.
Character-level tokenization fixes unknown words, since a small alphabet covers everything. The price is length: every word becomes several tokens, each carrying little meaning, and the model spends capacity rebuilding words from letters.
Subword tokenization sits between them. Frequent words stay whole and rare words are spelled from smaller known pieces, so "replayed" can be "re" plus "played". GPT-2, BERT, T5 and Llama all work this way. The Hugging Face tokenizer guide names three families: byte pair encoding (BPE), WordPiece (the BERT family) and Unigram (T5). SentencePiece runs BPE or Unigram on raw text and treats the space as an ordinary symbol, so it never assumes spaces separate words.
Vocabulary size is a trade-off. More entries mean shorter sequences but a bigger embedding table and more tokens too rare to learn well.
03Byte pair encoding from scratch
Byte pair encoding for text comes from Sennrich, Haddow and Birch (2015), who adapted a data compression algorithm to handle rare words in machine translation. Start with every word spelled as single characters plus an end-of-word marker. Count every adjacent pair across the corpus, weighted by how often each word appears. Merge the most frequent pair everywhere into one new symbol. Repeat. The number of merges is the one setting you choose, and the final vocabulary is the starting characters plus one new symbol per merge.
The code trains on a made-up 22-word corpus about playing.
from collections import Counter
def learn_bpe(words, num_merges):
# each word becomes a tuple of characters plus an end-of-word marker
vocab = Counter(tuple(w) + ("</w>",) for w in words)
merges = []
for _ in range(num_merges):
pairs = Counter()
for word, freq in vocab.items():
for a, b in zip(word, word[1:]):
pairs[a, b] += freq
if not pairs:
break
best = max(pairs, key=pairs.get) # ties: first pair counted wins
merges.append(best)
new_vocab = Counter()
for word, freq in vocab.items():
out, i = [], 0
while i < len(word):
if i + 1 < len(word) and (word[i], word[i + 1]) == best:
out.append(word[i] + word[i + 1]); i += 2
else:
out.append(word[i]); i += 1
new_vocab[tuple(out)] += freq
vocab = new_vocab
return merges
def encode(word, merges, alphabet):
symbols = [c if c in alphabet else "[UNK]" for c in word] + ["</w>"]
for a, b in merges: # replay merges in learned order
i = 0
while i < len(symbols) - 1:
if symbols[i] == a and symbols[i + 1] == b:
symbols[i:i + 2] = [a + b]
else:
i += 1
return symbols
corpus = ("the player played and the players play again "
"a replay of the play was displayed "
"she plays and he played the replay").split()
alphabet = set("".join(corpus))
merges = learn_bpe(corpus, 12)
for n, m in enumerate(merges, 1):
print(n, m)
for w in ["played", "replayed", "playful", "Play", "zebra"]:
print(w, "->", encode(w, merges, alphabet))Output:
1 ('p', 'l')
2 ('pl', 'a')
3 ('pla', 'y')
4 ('h', 'e')
5 ('he', '</w>')
6 ('play', 'e')
7 ('d', '</w>')
8 ('t', 'he</w>')
9 ('play', '</w>')
10 ('playe', 'd</w>')
11 ('s', '</w>')
12 ('playe', 'r')
played -> ['played</w>']
replayed -> ['r', 'e', 'played</w>']
playful -> ['play', 'f', '[UNK]', 'l', '</w>']
Play -> ['[UNK]', 'l', 'a', 'y', '</w>']
zebra -> ['[UNK]', 'e', '[UNK]', 'r', 'a', '</w>']Read the merge list top to bottom. "p" and "l" are the most common pair, then "pl" absorbs "a", then "y", so "play" is one symbol after three merges. By merge 10, "played" with its end marker is one token.
Encoding a new word replays the merges in the order they were learned, as Sennrich and colleagues describe for test time. That is why "replayed" comes out as "r", "e", "played": the corpus contains "replay" twice, but 12 merges were not enough to reach "re".
The last three lines are the failures worth remembering. "playful" contains a "u", which never appeared in training, so the tokenizer has no symbol for it and emits [UNK]. "Play" with a capital P fails the same way, because "P" and "p" are different characters. "zebra" loses two of its five letters. That information is gone before the model sees anything. Larger training corpora make this rarer, but a character-based vocabulary can always meet a symbol it lacks.
04Byte-level BPE and the cost of rare text
GPT-2 removed the unknown token by running BPE on bytes instead of characters. UTF-8 turns any text into bytes, and there are only 256 byte values, so a vocabulary that starts from them can encode every string. According to the Hugging Face guide, GPT-2's vocabulary is 50,257 entries: 256 bytes, 50,000 learned merges and one special end-of-text token.
The version below works on bytes and adds pre-tokenization: the text is first split into chunks of one word plus its leading space, and merges never cross a chunk boundary.
import re
from collections import Counter
def chunks(text):
return re.findall(r" ?\S+", text) # pre-split: a word plus its leading space
def merge(ids, pair, new_id):
out, i = [], 0
while i < len(ids):
if i + 1 < len(ids) and (ids[i], ids[i + 1]) == pair:
out.append(new_id); i += 2
else:
out.append(ids[i]); i += 1
return out
def learn_byte_bpe(text, num_merges):
words = Counter(tuple(c.encode("utf-8")) for c in chunks(text)) # base ids 0..255
merges = {}
for new_id in range(256, 256 + num_merges):
pairs = Counter()
for w, f in words.items():
for p in zip(w, w[1:]):
pairs[p] += f
if not pairs:
break
best = max(pairs, key=pairs.get)
merges[best] = new_id
words = Counter({tuple(merge(list(w), best, new_id)): f for w, f in words.items()})
return merges
def encode(text, merges):
out = []
for c in chunks(text):
ids = list(c.encode("utf-8"))
for pair, new_id in merges.items(): # replay merges in learned order
ids = merge(ids, pair, new_id)
out += ids
return out
def decode(ids, merges):
table = {i: bytes([i]) for i in range(256)}
for (a, b), new_id in merges.items():
table[new_id] = table[a] + table[b]
return b"".join(table[i] for i in ids).decode("utf-8")
corpus = ("the player played and the players play again "
"a replay of the play was displayed "
"she plays and he played the replay")
merges = learn_byte_bpe(corpus, 20)
print("learned:", [decode([i], merges) for i in merges.values()])
for s in [" played", " replayed", " players", " playful", " Play", " zebra", " café", " 日本語"]:
ids = encode(s, merges)
print(f"{s!r:10} chars={len(s)} bytes={len(s.encode()):2} tokens={len(ids):2} "
f"ids={ids} roundtrip={decode(ids, merges) == s}")
# skip pre-tokenization: the whole corpus becomes one chunk
chunks = lambda text: [text]
flat = learn_byte_bpe(corpus, 30)
print("no pre-split:", len(corpus.encode()), "bytes ->", len(encode(corpus, flat)), "tokens")
print("longest token:", repr(max((decode([i], flat) for i in flat.values()), key=len)))Output:
learned: ['pl', 'pla', 'play', ' play', 'he', 'the', ' playe', ' a', ' the', ' player', ' played', ' an', ' and', ' r', ' re', ' replay', ' players', ' ag', ' aga', ' agai']
' played' chars=7 bytes= 7 tokens= 1 ids=[266] roundtrip=True
' replayed' chars=9 bytes= 9 tokens= 3 ids=[271, 101, 100] roundtrip=True
' players' chars=8 bytes= 8 tokens= 1 ids=[272] roundtrip=True
' playful' chars=8 bytes= 8 tokens= 4 ids=[259, 102, 117, 108] roundtrip=True
' Play' chars=5 bytes= 5 tokens= 5 ids=[32, 80, 108, 97, 121] roundtrip=True
' zebra' chars=6 bytes= 6 tokens= 6 ids=[32, 122, 101, 98, 114, 97] roundtrip=True
' café' chars=5 bytes= 6 tokens= 6 ids=[32, 99, 97, 102, 195, 169] roundtrip=True
' 日本語' chars=4 bytes=10 tokens=10 ids=[32, 230, 151, 165, 230, 156, 172, 232, 170, 158] roundtrip=True
no pre-split: 114 bytes -> 26 tokens
longest token: 'the player played and the players play again a replay'" played" and " players" are now single ids, 266 and 272. " replayed" is " replay" plus "e" and "d", ids 271, 101 and 100, the ones in the diagram. Every line decodes back to the exact input, so the [UNK] problem is gone. " Play" still costs five tokens because no merge involves a capital P, but it costs tokens, not information.
The catch is cost. Each character of "日本語" takes three bytes in UTF-8 and this tokenizer never saw Japanese, so three characters plus a space cost ten tokens. A tokenizer trained on plenty of Japanese would learn merges for it, but the mechanism is general: text that was rare in the tokenizer's training data splits into more pieces, so a context window holds less of it and per-token pricing charges more. The ratio depends on tokenizer and text, so measure it with the tokenizer you actually use.
Pre-tokenization matters too. The last lines of the script replace chunks with a function that returns the whole text as one chunk, then train 30 merges. The 114-byte corpus shrinks to 26 tokens, and the longest token is the 53-character run "the player played and the players play again a replay". That is memorisation, not a vocabulary.
05Embeddings: a lookup table that learns
The embedding table is a matrix with one row per vocabulary entry and d columns. Looking up id 271 means reading row 271, which is the same as multiplying a one-hot vector (all zeros except a 1 at position 271) by the table; the next section's code checks this. Libraries index the row directly because it is cheaper.
The table starts random. Gradient descent nudges the rows of tokens in each batch so predictions improve, and tokens used in similar contexts drift toward similar rows.
Three kinds of embedding come up in interviews.
Static word embeddings give each word one fixed vector, whatever sentence it is in. Mikolov and colleagues (2013) proposed two architectures for learning such vectors cheaply; their paper reports training on 1.6 billion words in under a day. The weakness is that "bank" gets one vector for both the river and the money sense.
Contextual embeddings are what a transformer's layers output. The input row for "bank" is still one row, but each later layer mixes in the surrounding tokens, so the two senses separate. The lookup itself ignores word order; position information is added separately, as the transformers and self-attention topic explains.
Sentence embeddings compress a whole sentence into one vector. Reimers and Gurevych (2019) motivate Sentence-BERT with numbers: finding the most similar pair among 10,000 sentences by running every pair through BERT takes about 50 million inference computations, roughly 65 hours, while embedding each sentence once and comparing with cosine similarity takes about 5 seconds in their setup.
One rule follows: vectors from different models live in different spaces, so comparing them yields a meaningless number.
06Measuring similarity with cosine
The script below builds a toy embedding to show similarity emerging from counts alone. It is not word2vec. It counts which words appear within two positions of each other in twelve short sentences, takes the log of the counts, and keeps the top four directions of a singular value decomposition as 4-dimensional vectors.
import numpy as np
sentences = [
"the cat chased the mouse", "the dog chased the cat", "a dog likes to bark",
"the cat likes to purr", "my dog and my cat sleep", "the puppy and the kitten sleep",
"the car needs fuel", "the truck needs fuel", "a car drives on the road",
"a truck drives on the road", "she parked the car", "he parked the truck",
]
toks = [s.split() for s in sentences]
vocab = sorted({w for t in toks for w in t})
idx = {w: i for i, w in enumerate(vocab)}
# count how often two words appear within 2 positions of each other
C = np.zeros((len(vocab), len(vocab)))
for t in toks:
for i, w in enumerate(t):
for j in range(max(0, i - 2), min(len(t), i + 3)):
if i != j:
C[idx[w], idx[t[j]]] += 1
U, S, _ = np.linalg.svd(np.log1p(C))
E = U[:, :4] * S[:4] # embedding table: one 4-d row per word
def cos(a, b):
return a @ b / (np.linalg.norm(a) * np.linalg.norm(b))
print("vocab size:", len(vocab), "table shape:", E.shape)
for a, b in [("cat", "dog"), ("car", "truck"), ("cat", "car"), ("dog", "truck")]:
print(f"cos({a}, {b}) = {cos(E[idx[a]], E[idx[b]]):+.3f}")
# an embedding lookup is the same as multiplying a one-hot vector by the table
one_hot = np.zeros(len(vocab)); one_hot[idx["cat"]] = 1
print("one-hot @ E equals row lookup:", np.allclose(one_hot @ E, E[idx["cat"]]))
# cosine ignores length, dot product does not
q = np.array([1.0, 1.0]); short = np.array([1.0, 0.9]); long_ = np.array([5.0, 1.0])
for name, v in [("short", short), ("long", long_)]:
print(f"{name:5} dot={q @ v:5.2f} cosine={cos(q, v):.3f}")Output:
vocab size: 25 table shape: (25, 4)
cos(cat, dog) = +0.998
cos(car, truck) = +1.000
cos(cat, car) = +0.428
cos(dog, truck) = +0.412
one-hot @ E equals row lookup: True
short dot= 1.90 cosine=0.999
long dot= 6.00 cosine=0.832"cat" and "dog" nearly coincide because both sit near "the", "chased", "likes" and "my". "car" and "truck" share "needs", "drives" and "parked". The animal-vehicle pairs score about 0.4. Values this close to 1.0 come from the tiny, repetitive corpus; the ordering is the point.
Cosine similarity is the dot product divided by both vector lengths, which equals the cosine of the angle between them. In the last two lines the "long" vector wins on dot product, 6.00 against 1.90, purely because it is long, while the "short" one points almost the same way as the query, cosine 0.999 against 0.832. When length reflects something unrelated to meaning, cosine ranks more fairly. If every vector is normalised to length 1 first, the dot product and cosine are the same number, so normalising once and then using the cheaper dot product is a safe shortcut.
A high cosine score means two texts were used in similar contexts. It does not mean they agree. Opposites such as "hot" and "cold" appear in very similar contexts, so they can score high for exactly that reason.
07Common interview questions
Q: Why do language models use subword tokens instead of words or characters?
A: Words give a huge vocabulary and [UNK] for anything unseen. Characters make sequences long. Subwords keep common words whole and build rare ones from known pieces; with byte-level BPE nothing is ever unknown.
Q: How does BPE training work, and how is a new word encoded?
A: Start from characters or bytes, repeatedly merge the most frequent adjacent pair, and stop after a chosen number of merges. To encode, apply the learned merges in the same order. In the demo, 12 merges were enough to make "played" one token but left "replayed" as "r", "e", "played".
Q: What is the difference between BPE, WordPiece and Unigram?
A: BPE merges the most frequent pair. WordPiece, used by BERT-style models, merges the pair with the highest freq(ab) / (freq(a) * freq(b)), which favours pairs that occur together more than their parts would predict. Unigram goes the other way: it starts with a large vocabulary and removes the tokens whose removal hurts a likelihood-based loss the least.
Q: What happens to a word the tokenizer has never seen?
A: With word-level or character-level BPE, unseen symbols become [UNK] and their information is lost. Byte-level BPE starts from all 256 byte values, so any string can be encoded and decoded exactly; an unfamiliar word or script just costs more tokens.
Q: Why might an LLM miscount the letters in a word?
A: A plausible explanation, not a proven one: the model receives token ids, not letters. In the byte-level demo, " players" became the single id 272, so the letters are never presented as separate inputs. Spelling has to be learned per token, and that knowledge can be patchy.
Q: Why use cosine similarity for embeddings rather than the raw dot product?
A: Cosine measures only the angle, so length cannot inflate the score. Above, a longer vector won on dot product (6.00 vs 1.90) while the better-aligned vector won on cosine (0.999 vs 0.832). For unit-length vectors the two are identical.