Description

1. From Raw Text to Vectors: The End-to-End Pipeline

Raw Text:       "Tokenization is magic!"
                     │
                     ▼  [1. Pre-tokenization & UTF-8 Byte Mapping]
Pieces:         ["Token", "ization", " is", " magic", "!"]
                     │
                     ▼  [2. BPE Vocabulary Lookup (V ≈ 32k–128k)]
Token IDs:      [  3401,     2934,    374,    11290,   0 ]
                     │
                     ▼  [3. Embedding Matrix Lookup: E ∈ ℝ^(V × d_model)]
Dense Vectors:  [ e_3401,   e_2934,  e_374,  e_11290, e_0 ]   (each vector ∈ ℝ^4096)

2. Why Subword Tokenization (BPE)?

3. How Byte-Pair Encoding (BPE) Works (Simple → Advanced)

1. Start with Base Vocabulary: In modern Byte-Level BPE (tiktoken), the initial vocabulary is the 256 raw UTF-8 bytes (so no <UNK> token is ever needed).

2. Pre-tokenization Regex Split: Before merging, a regex pattern (such as GPT-4's cl100k_base / o200k_base regex) prevents merges across incompatible boundaries (e.g., preventing "dog!" from merging into a single token so punctuation stays separate from words).

3. Iterative Pair Counting & Merging (Training):
• Count all adjacent token pairs (a, b) across the training corpus.
• Find the most frequent pair .
• Mint a new token , add to the vocabulary, and replace all occurrences of with .
• Repeat until vocabulary size reaches target (e.g., in Llama-3).

4. Inference (Encoding): Apply the learned merge rules in the exact priority order they were learned during training (not by longest-prefix match!).

4. What Are Embeddings? (Geometric Meaning)

• We convert into a one-hot vector and multiply by the learnable Token Embedding Matrix :

• Static vs. Contextual Embeddings:
• Input Embedding (): Static lookup—the word "bank" gets the exact same initial vector whether in "river bank" or "investment bank".
• Contextual Hidden States (): After passing through Transformer self-attention layers, the vector for "bank" is dynamically pulled toward "water/shore" or "finance/loan".

• Weight Tying: Many LLMs share (tie) the input embedding matrix with the final output language modeling head to save hundreds of millions of parameters and regularize training.

Learning notes

Visual Walkthrough: Training BPE by Hand

• "hug" h u g

• "pug" p u g

• "pun" p u n

• "bun" b u n

Base Vocabulary: { 'b', 'g', 'h', 'n', 'p', 'u' }  (6 tokens)

Step 1: Count adjacent pairs
  ('u', 'g') = 10 (hug) + 5 (pug) = 15
  ('u', 'n') = 12 (pun) + 4 (bun) = 16
  ('p', 'u') =  5 (pug) + 12 (pun) = 17  <-- HIGHEST FREQUENCY!
  ('h', 'u') = 10, ('b', 'u') = 4
  => Merge Rule #1: ('p', 'u') -> 'pu'
  Corpus becomes: h u g (10), pu g (5), pu n (12), b u n (4)

Step 2: Recount adjacent pairs
  ('u', 'n') = 4 (only in b u n now!)
  ('pu', 'n') = 12
  ('u', 'g') = 10 (only in h u g now!)
  ('pu', 'g') = 5
  ('h', 'u') = 10
  => Merge Rule #2: ('pu', 'n') -> 'pun'
  Corpus becomes: h u g (10), pu g (5), pun (12), b u n (4)

Step 3: Recount adjacent pairs
  ('h', 'u') = 10, ('u', 'g') = 10  (Tie! Pick ('u', 'g') -> 'ug')
  => Merge Rule #3: ('u', 'g') -> 'ug'
  Corpus becomes: h ug (10), pu g (5), pun (12), b u n (4)

Advanced Nuances & Real-World Quirks in LLMs

Comparison of Subword Algorithms

Example or implementation

Minimal BPE Tokenizer + PyTorch Embedding Pipeline From Scratch

from collections import Counter
import torch
import torch.nn as nn

# ==========================================
# PART 1: Minimal Byte-Level BPE From Scratch
# ==========================================
class MinimalBPE:
    def __init__(self, vocab_size: int = 270):
        assert vocab_size >= 256, "Base byte vocab requires at least 256 tokens."
        self.vocab_size = vocab_size
        self.merges = {}  # (int, int) -> new_token_id
        self.vocab = {i: bytes([i]) for i in range(256)}

    @staticmethod
    def _get_pair_counts(ids: list[int]) -> Counter:
        return Counter(zip(ids, ids[1:]))

    @staticmethod
    def _merge_pair(ids: list[int], pair: tuple[int, int], new_id: int) -> list[int]:
        merged = []
        i = 0
        while i < len(ids):
            if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
                merged.append(new_id)
                i += 2
            else:
                merged.append(ids[i])
                i += 1
        return merged

    def train(self, text: str):
        ids = list(text.encode("utf-8"))
        num_merges = self.vocab_size - 256
        for i in range(num_merges):
            counts = self._get_pair_counts(ids)
            if not counts:
                break
            best_pair = max(counts, key=counts.get)
            new_id = 256 + i
            ids = self._merge_pair(ids, best_pair, new_id)
            self.merges[best_pair] = new_id
            self.vocab[new_id] = self.vocab[best_pair[0]] + self.vocab[best_pair[1]]

    def encode(self, text: str) -> list[int]:
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            # Find the pair in `ids` with the lowest merge index (highest priority)
            pairs = set(zip(ids, ids[1:]))
            candidate = min(
                pairs, key=lambda p: self.merges.get(p, float("inf"))
            )
            if candidate not in self.merges:
                break
            ids = self._merge_pair(ids, candidate, self.merges[candidate])
        return ids

    def decode(self, ids: list[int]) -> str:
        raw_bytes = b"".join(self.vocab[idx] for idx in ids)
        return raw_bytes.decode("utf-8", errors="replace")

# Test BPE Training & Encoding
corpus = "low lower lowest new newer newest low lower lowest"
tokenizer = MinimalBPE(vocab_size=265)
tokenizer.train(corpus)
encoded_ids = tokenizer.encode("lowest newer")
print("Encoded Token IDs:", encoded_ids)
print("Decoded Text:", tokenizer.decode(encoded_ids))

# ==========================================
# PART 2: PyTorch Embedding & Cosine Similarity
# ==========================================
vocab_size, d_model = 265, 64
embedding_layer = nn.Embedding(num_embeddings=vocab_size, embedding_dim=d_model)

input_tensor = torch.tensor([encoded_ids], dtype=torch.long)  # Shape: [batch=1, seq_len]
embedded = embedding_layer(input_tensor)                      # Shape: [1, seq_len, 64]
print("Output Embedding Shape:", embedded.shape)

Interview-ready explanation

2-Minute Verbal Script (Say This Aloud Without Notes)

"Tokenization and embeddings form the input-output boundary of every LLM. Because neural networks operate on continuous vectors rather than raw strings, we first segment text into discrete subword units using Byte-Pair Encoding (BPE).

Why subwords? Character-level tokenization creates sequences that are too long for quadratic attention, while word-level tokenization suffers from massive vocabularies and out-of-vocabulary failures on rare words or code. Byte-level BPE starts with the 256 UTF-8 bytes as its base vocabulary and iteratively merges the most frequent adjacent pairs during training until reaching a target vocabulary size—typically 32,000 to 128,000 tokens. Because every string decomposes into UTF-8 bytes in the worst case, Byte-level BPE has a zero out-of-vocabulary rate.

At inference time, we apply a pre-tokenization regex to keep punctuation and digits cleanly separated, run our learned BPE merges in priority order to get integer Token IDs, and pass those IDs into a learnable Embedding Matrix of shape . Each token ID simply indexes a row in that matrix, converting a discrete integer into a dense vector in .

Importantly, this initial embedding is static—the word 'apple' gets the same input vector whether it refers to the fruit or the tech company. As the vector flows through the Transformer's self-attention layers, it absorbs surrounding tokens to become a contextualized representation, before finally projecting back to vocabulary logits via the output unembedding matrix."

Questions to revisit

• Q1: How do you choose the optimal vocabulary size (e.g., 32k in LLaMA-2 vs. 128k in LLaMA-3)?
• Answer: Larger compresses text into fewer tokens (reducing sequence length , which quadratically speeds up attention and expands effective context length, especially for code and multilingual text). However, it increases the size of the embedding and unembedding matrices ( parameters) and makes the final Softmax layer more memory-bandwidth heavy, while leaving rare tokens under-trained.

• Q2: Why do we need a pre-tokenization regex in GPT-2/GPT-4 (tiktoken) before running BPE merges?
• Answer: Without regex splitting, high-frequency words followed by punctuation ("the,", "the.", "the!", "the?") would merge into separate vocabulary tokens, wasting vocabulary slots on combinatorial punctuation variants and hurting generalization.

• Q3: What are "glitch tokens" (like SolidGoldMagikarp) and how do they happen?
• Answer: If the BPE tokenizer is trained on a scrape containing repetitive strings (e.g., Reddit usernames or log dumps) that are subsequently filtered out of the LLM's pretraining corpus, those token IDs exist in the vocabulary but never receive gradient updates during pretraining—leaving their embeddings stuck near random initialization and causing erratic outputs when triggered.