Tokenization: From Text to Token IDs

1. Quick anchor

A transformer never sees text. It sees integers. Tokenization is the deterministic function that maps a UTF-8 string to a list of integer IDs (and back), and it is the only lossy, learned-but-frozen layer in the stack that you typically cannot fine-tune away. The dominant scheme — byte-level BPE — starts from the 256 raw bytes and greedily merges the most frequent adjacent pairs into a fixed vocabulary of subword "tokens," so common words become one token and rare strings shatter into many. This is why token counts are not word counts (your bill and your context window are denominated in tokens), why the model "can't spell" (it sees straw+berry, not letters), and why a single corrupted training token can make a frontier model babble. Get the tokenizer wrong and you pay for it in every forward pass, in every language, forever.

2. Why interviewers probe this

• IC3 — Can you explain why len(text) ≠ token count, why digits and rare words cost more, and the basic spelling/counting failure mode? Do you reach for tiktoken before guessing context limits? This is table-stakes literacy: people who skip it ship code that silently truncates prompts.
• IC4 — Can you implement BPE from scratch (greedy merge loop, byte-level base, encode by replaying merges in learned order)? Do you know the WordPiece vs. BPE vs. Unigram distinctions and what each optimizes? Can you reason about vocab-size tradeoffs in terms of embedding-matrix memory vs. sequence length?
• IC5 — Can you connect tokenization to system-level outcomes: multilingual fairness and cost (BPE over-fragments low-resource languages), context-window economics, glitch tokens as a training/data-hygiene failure, and the architectural bet that tokenizer-free / byte-level models are making? Do you know when retraining the tokenizer is worth a full pretrain and when a vocab-extension hack suffices?

3. Concept build-up

3.1 Why subwords at all — the three bad extremes

Imagine three naive vocabularies. Characters/bytes: vocab of ~256, never OOV, but a 1,000-character sentence becomes ~1,000 tokens — attention is O(N²), so you've made every forward pass catastrophically expensive. Whole words: short sequences, but English alone has millions of word forms; you'd need a huge embedding matrix, and you'd still hit OOV on antidisestablishmentarianism, typos, and every new product name. Subwords are the Goldilocks point: frequent words get one token (the → 1), rare words decompose into reusable pieces (tokenization → token+ization), and nothing is ever OOV if you work at the byte level. The whole game is choosing where to put the vocabulary's finite "budget."

3.2 BPE: greedy bottom-up merges

BPE (Sennrich et al., 2016, originally for machine translation) builds the vocab bottom-up. Start with bytes; count adjacent pairs over the corpus; merge the most frequent pair into a new symbol; repeat. The learned artifact is an ordered list of merge rules. The order matters enormously: to encode new text you replay merges in the order they were learned, because earlier merges are the high-frequency building blocks later merges depend on.

A subtlety that trips people up: BPE pre-tokenizes on word boundaries (via regex) first, so merges never fuse across spaces or punctuation. That's why dog. and dog tokenize differently, and why a leading space is part of the token ( the is a distinct token from the). This boundary handling is exactly where BPE's known failure mode lives — when a high-frequency pair straddles a morpheme boundary, you get linguistically nonsensical splits.

3.3 Byte-level BPE — the GPT trick

GPT-2 (Radford et al., 2019) made one decision that every frontier lab copied: run BPE over bytes, not Unicode characters. The base vocabulary is the 256 possible byte values. Because UTF-8 encodes every possible string as bytes, byte-level BPE can round-trip emoji, Chinese, malformed Unicode, and binary garbage with zero OOV tokens — there is literally no input it can't represent. (GPT-2 added a clever byte-to-printable-char remapping so control bytes don't break the regex, but conceptually the base is bytes.) The cost: a single non-ASCII character is multiple bytes, so café or 日本語 cost more tokens than their character count suggests — a multibyte character that didn't get merged stays as 2–4 separate byte tokens. This is the seed of the multilingual inequity we'll hit in §5.

3.4 SentencePiece, Unigram, and WordPiece — the alternatives

Three siblings you must be able to contrast:

• SentencePiece (Kudo & Richardson, 2018) is a framework, not an algorithm. Its real innovation: treat the raw input as a stream of Unicode characters with spaces escaped as a visible ▁ token, so tokenization is fully reversible and language-agnostic (no reliance on whitespace, which matters for Chinese/Japanese/Thai that don't space-separate words). It can run either BPE or Unigram underneath. Used by T5, Gemma, Llama (Llama 2 used SentencePiece-BPE).

• Unigram LM (Kudo, 2018) goes top-down instead of bottom-up: start with a huge candidate vocab, assign each token a probability, then iteratively prune the tokens whose removal least hurts the corpus likelihood under a unigram language model. At encode time it picks the segmentation with highest total probability (via Viterbi), and during training it can sample alternate segmentations ("subword regularization") as data augmentation. It tends to produce more linguistically clean splits than greedy BPE.

• WordPiece (BERT, Google) is BPE's cousin: same greedy bottom-up merging, but instead of merging the most frequent pair, it merges the pair that most increases corpus likelihood — roughly, it maximizes count(ab) / (count(a)·count(b)), favoring pairs that are "surprisingly" common rather than merely frequent. It marks word-interior pieces with ## (playing → play, ##ing).

3.5 Why token count ≠ word count (and why it's your bill)

Three forces decouple tokens from words. (1) Common words are one token, rare words are many — the is 1, antidisestablishmentarianism might be 6+. (2) Leading spaces and case create distinct tokens — The, the, the, THE can be four different IDs, so the same word costs differently by position. (3) Non-English and code over-fragment — a language poorly represented in the training corpus never got its frequent pairs merged, so it falls back toward raw bytes. A rough English heuristic is ~0.75 words per token (≈1.3 tokens/word), but treat it as a guess: always measure with the real tokenizer (tiktoken, or the HF tokenizers for the model you actually use). This number is your economics — context windows, API pricing, and prefill latency are all denominated in tokens, not words.

4. Minimal implementation

The file examples/transformers/bpe.py is a complete, runnable byte-level BPE — train, encode, decode, with round-trip assertions. It's the same algorithm as tiktoken, minus the regex pre-tokenizer and Rust. The core is three functions: count pairs, merge a pair, and replay merges in learned order.

from collections import Counter
 
def get_pair_counts(ids_per_word):
    counts = Counter()
    for ids, freq in ids_per_word:
        for a, b in zip(ids, ids[1:]):
            counts[(a, b)] += freq          # weight by word frequency
    return counts
 
def merge(ids, pair, new_id):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i+1]) == pair:
            out.append(new_id); i += 2      # collapse the pair
        else:
            out.append(ids[i]); i += 1
    return out
 
def train(text, vocab_size):
    merges, vocab = {}, {i: bytes([i]) for i in range(256)}   # byte-level base
    word_freqs = Counter(text.split())                        # pre-tokenize
    ids_per_word = [(list((" " + w).encode()), f) for w, f in word_freqs.items()]
    for step in range(vocab_size - 256):
        counts = get_pair_counts(ids_per_word)
        if not counts: break
        best = max(counts, key=counts.get)                    # greedy
        if counts[best] < 2: break
        new_id = 256 + step
        merges[best] = new_id
        vocab[new_id] = vocab[best[0]] + vocab[best[1]]
        ids_per_word = [(merge(ids, best, new_id), f) for ids, f in ids_per_word]
    return merges, vocab

Running the full file on a tiny corpus prints the first merges and tokenizes test strings:

learned 30 merges, vocab size 286
  merge  0: (116, 104) -> 256  ('th')
  merge  1: (256, 101) -> 257  ('the')
  merge  2: (32, 257)  -> 258  (' the')
  merge  6: (261, 259) -> 262  (' cat')
'the cat'    -> 2 tokens  [258, 262]
'running'    -> 1 tokens  [281]
'strawberry' -> 10 tokens  [265, 116, 114, 97, ...]   # unseen → shatters to bytes
'café'       -> 5 tokens   # 'é' is 2 UTF-8 bytes, never merged

Three things to notice, each load-bearing for the interview. (1) Order is the model: th (256) must be learned before the (258) can form — encoding replays merges by ascending ID. (2) Byte-level = no OOV: strawberry, absent from this corpus, doesn't error — it gracefully degrades to byte tokens. (3) é costs 2 byte tokens because it's 2 UTF-8 bytes that never got frequent enough to merge — the multilingual tax in miniature. The encoder applies the globally earliest applicable merge each pass (min by merge ID), which is the standard greedy BPE encode; production tiktoken does the same with a faster priority-queue inner loop.

5. Production tradeoffs

Cost & latency. The vocab sits in two places: the embedding table (in) and the LM head (out), each vocab_size × d_model. At 200k vocab and d_model 4096 in fp16 that's ~1.6 GB per table — a real chunk of a small model's footprint and a fatter softmax every decode step. Against that, a bigger vocab packs more characters per token, so sequences are shorter, attention's O(N²) is cheaper, and you fit more content in a fixed context window. Llama 3 jumped to a 128k vocab (from Llama 2's 32k) precisely to shorten sequences and improve multilingual/code efficiency; GPT-4o went to ~200k. The crossover is empirical: past a point, extra vocab entries are rare tokens whose embeddings are under-trained and whose memory cost outweighs the sequence-length win.

The multilingual failure mode (the IC5 trap). A tokenizer trained on English-dominated data never merged the frequent pairs of low-resource languages, so Hindi or Burmese text falls back toward raw bytes — the same sentence can cost 2–5× more tokens than its English translation. That's a triple penalty: users pay more, fit less context, and the model effectively sees their language at lower resolution (each token carries less meaning), which degrades quality. This is a fairness and cost problem baked into a frozen artifact. Mitigations: train the tokenizer on a balanced multilingual corpus from day one (best, but requires committing before pretrain), parity-aware BPE that caps per-language fragmentation, or — post-hoc — vocab extension: add new tokens for the underserved language and continue-pretrain only the new embedding rows. Extension is cheap but the new tokens start under-trained and never integrate as cleanly as native ones.

Glitch tokens (the data-hygiene failure). A token can exist in the vocab but be almost absent from training text — classically because the tokenizer corpus and the model corpus differed, or because a Reddit-username string (SolidGoldMagikarp, _davidjl) was frequent enough to earn a merge but then got filtered out of pretraining. Its embedding is essentially random/untrained, so prompting the model with it produces bizarre, off-distribution behavior — evasion, hallucination, or spelling something entirely different (Rumbelow & Watkins, 2023). The fix is process: build the tokenizer and the model on the same cleaned corpus, and audit low-frequency token embeddings.

The bet at scale. Tokenization is increasingly seen as a wart — it's why models can't do character-level tasks, it bakes in language bias, and it's a non-differentiable seam in an otherwise end-to-end system. Byte-level / tokenizer-free architectures (e.g. byte-latent approaches that dynamically group bytes) are an active research direction; as of mid-2026 they're not yet the production default — the O(N²) cost of long byte sequences is the blocker — but it's the direction a strong IC5 should name. See /inference for how token granularity drives KV-cache and throughput math, and /context-engineering for budgeting tokens in long prompts.

6. How it's asked

7. Pitfalls & flashcards

• Don't estimate context budgets from word/char counts. Always tokenize with the exact tokenizer of the model you'll call (tiktoken for OpenAI, the HF tokenizers for the open model). A 0.75-words-per-token rule of thumb is fine for English back-of-envelope and wrong for code, JSON, and non-English.
• Leading spaces and case matter. The, the, THE can be distinct tokens; few-shot prompt formatting that changes spacing can change tokenization and behavior.
• Numbers and code fragment unpredictably. Multi-digit tokens make arithmetic brittle; don't rely on the model "seeing" individual digits.
• Multilingual = more tokens = more cost + lower quality. Measure tokens-per-character per language before claiming a model is "multilingual."
• Tokenizer and model corpora must match or you breed glitch tokens. Audit rare-token embeddings.
• Vocab size is a memory-vs-sequence-length tradeoff, not a free quality dial — past the useful range you're paying for under-trained rare-token embeddings.

Flashcard. BPE = start from 256 bytes, greedily merge the most frequent adjacent pair into a new token, repeat to target vocab; encode by replaying merges in learned order. Byte-level ⇒ zero OOV. Token count ≠ word count, and that delta is your cost, context, and multilingual fairness.

8. Further reading

• Sennrich, Haddow & Birch (2016), Neural Machine Translation of Rare Words with Subword Units — the original BPE-for-NLP paper: https://arxiv.org/abs/1508.07909
• Radford et al. (2019), Language Models are Unsupervised Multitask Learners (GPT-2) — byte-level BPE in practice: https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf
• Kudo & Richardson (2018), SentencePiece — language-agnostic, reversible tokenization: https://arxiv.org/abs/1808.06226
• Kudo (2018), Subword Regularization — the Unigram LM tokenizer: https://arxiv.org/abs/1804.10959
• Rumbelow & Watkins (2023), SolidGoldMagikarp — glitch tokens and the tokenizer/corpus mismatch: https://www.lesswrong.com/posts/aPeJE8bSo6rAFoLqg/solidgoldmagikarp-plus-prompt-generation

Next: Self-attention and the QKV mechanism — once text is IDs, the embedding table turns them into vectors and attention does the rest.