Building a Byte-Level BPE Tokenizer from Scratch

1.2 Why Traditional Tokenization Approaches Collapsed

In the early history of natural language processing, researchers experimented with two naive tokenization paradigms, both of which carried catastrophic trade-offs:

| Tokenization Scheme | Splitting Example ("unbelievable") | Primary Advantage | Fatal Engineering Flaw | | 1. Word-Level Tokenization | ["unbelievable"] (Full words stored in dictionary) | Intuitive and aligns with human vocabulary | 1. Unbounded vocabulary explosion (cannot cover millions of words)<br>2. Encounters typos and new words as <UNK> garble | | 2. Character-Level Tokenization | ['u', 'n', 'b', 'e', 'l', ...] (Only individual characters) | Tiny base vocabulary (dozens to thousands) | 1. Extreme sequence length bloat (one word takes 12 tokens)<br>2. Exhausts context windows quickly; individual characters lack semantic depth | | 3. Byte-Level BPE | ["un", "believ", "able"] (256 byte atoms + greedy merging) | The Golden Balance: High-frequency words compress into single tokens, rare words decompose into byte atoms | Solves both flaws simultaneously; the universal industry benchmark for modern LLMs |

💡 Core Intuition: Chemistry of Atoms and Molecules

• Why will Byte-Level BPE never produce an unknown token <UNK> error?
• In Byte-Level BPE, we initialize the 256 fundamental bytes (values $0 \sim 255$) as IDs 0 through 255 in our vocabulary.
• Because every character across every human language decomposes into combinations of these 256 bytes, even if the model encounters ancient hieroglyphs or newly minted internet slang, the tokenizer simply falls back to emitting raw bytes—it can never crash or throw an OOV error!
• How does it compress sequence lengths?
• When two bytes frequently co-occur (such as 't' and 'h'), the algorithm merges them into a brand-new molecule 'th';
• When the 3 bytes making up Chinese '中' regularly appear together, BPE fuses those 3 bytes into a single token ID!

1.3 Paper Derivation: How Was the BPE Algorithm Invented?

Putting aside dense academic formulas, let us take pen and paper and trace through a complete BPE training cycle by hand.

Initial Corpus State

Suppose our miniature training corpus contains only 4 words, with their occurrence frequencies indicated on the right:

• "low": 5 times
• "lower": 2 times
• "newest": 6 times
• "widest": 3 times

Step 1: Disassemble Everything into Single Character Atoms

Insert spaces between each character to restore all words to their atomic representations:

• l o w (5 times)
• l o w e r (2 times)
• n e w e s t (6 times)
• w i d e s t (3 times)

Step 2: Scan Adjacent Pairs and Count Frequencies

Acting like a detective, tally how often every adjacent pair of symbols occurs across the corpus:

• (e, s): Occurs 6 times in "newest" + 3 times in "widest" $\to$ Total 9 times!
• (s, t): Occurs 6 times in "newest" + 3 times in "widest" $\to$ Total 9 times!
• (l, o): Occurs 5 times in "low" + 2 times in "lower" $\to$ Total 7 times.
• (o, w): Occurs 5 times in "low" + 2 times in "lower" $\to$ Total 7 times.

Which pair is the champion with the highest frequency? Clearly, it is (e, s) (tied with (s, t) at 9 occurrences)!

Step 3: Issue a New ID and Execute the First Merge!

We weld all e and s symbols together across the corpus to forge a brand-new composite Token: "es"! The corpus updates to:

• l o w
• l o w e r
• n e w [es] t (6 times)
• w i d [es] t (3 times)

Step 4: Advance to the Next Iteration!

Scanning the updated corpus reveals that the pair ([es], t) now appears $6 + 3 = 9$ times across two words! We execute another merge, creating "est" (ID 257)!

Notice the profound elegance: Without requiring any linguistic grammar dictionaries, BPE relies purely on probability statistics to naturally extract high-frequency roots, affixes, and complete words!

1.4 Pre-tokenization Regex: Why Must We Use the "Kitchen Knife"?

When beginners hand-code BPE, they frequently encounter an inexplicable severe bug: punctuation marks become glued to adjacent words, merging "apple." as a single token instead of separating "apple" and "."!

===================================================================================
                   未加预分词 (No Pre-tokenization) 导致的灾难
===================================================================================
语料里有两句话:
  "I eat an apple. You eat an apple."

BPE 统计全局文本时发现: "apple" 后面经常跟着 "."
结果: BPE 强行把它们焊死在了一起，生成了一个新 Token: "apple." (带句号的苹果)

灾难后果:
  下次用户向模型提问: "Do you like apple?" (句末是问号)
  此时模型查遍词表，只认识带句号的 "apple."，根本无法复用 "apple" 的语义！
===================================================================================

💡 The Kitchen Knife Principle: Pre-tokenization

To resolve this boundary pollution, modern GPT and LLaMA models deploy a regular expression kitchen knife before merging: segmenting raw continuous text into isolated ingredients:

• Words form isolated chunks (e.g., "apple")
• Punctuation marks form isolated chunks (e.g., ",", ".", "?")
• Whitespaces form isolated chunks
• Numbers form isolated chunks

Core Iron Rule: BPE merges are strictly confined within each individual chunk, and are strictly forbidden from crossing punctuation and word boundaries!

Anatomical Breakdown of the Classic Pre-tokenization Regex:

SPLIT_REGEX = re.compile(r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

• '(?:[sdmt]|ll|ve|re): Isolates English contractions (such as 've in I've, 's in it's);
• ?\p{L}+: Matches an optional leading space + consecutive letters (Chinese characters and Latin alphabets);
• ?\p{N}+: Matches numeric digits (guaranteeing numbers like 100 do not attach haphazardly);
• ?[^\s\p{L}\p{N}]+: Matches punctuation marks and various Emoji symbols.

1.5 Implementing the Tokenizer Line by Line in Pure Python

Now let us translate algorithmic theory into production code. Open src/tokenizer.py in your workspace and follow along line by line:

Module 1: Class Initialization and Foundational Atoms

class ByteBpeTokenizer:
    SPLIT_REGEX = SPLIT_REGEX

    def __init__(self):
        # 1. 必须准备的 4 个特殊标记 (Special Tokens)
        self.special_tokens = ["<pad>", "<s>", "</s>", "<unk>"]
        self.pad_token_id = 0  # 占位补齐符：用于短文本补齐
        self.bos_token_id = 1  # 句子开始符 (Beginning of Sequence)
        self.eos_token_id = 2  # 句子结束符 (End of Sequence)
        self.unk_token_id = 3  # 兜底未知符

        # 2. 映射字典
        self.vocab: Dict[int, bytes] = {}            # 数字 ID -> 原始字节串
        self.token_to_id: Dict[bytes, int] = {}      # 原始字节串 -> 数字 ID
        self.merges: Dict[Tuple[int, int], int] = {} # 记录合并规则: (id_a, id_b) -> 新合并ID

        # 3. 初始化地基
        self._init_base_vocab()

Mentor Q&A: Why Do Special Tokens Matter?

• For instance, during autoregressive generation, how does the model know when a passage is complete? It relies on emitting the </s> (EOS) end-of-sequence token!
• The moment the model produces </s>, the outer inference loop triggers a break statement to halt generation.

Next, let us inspect the foundational initialization function _init_base_vocab:

    def _init_base_vocab(self):
        """装入 4 个特殊标记和 256 个基础字节原子"""
        current_id = 0
        # 先存特殊标记 (占用 ID 0, 1, 2, 3)
        for st in self.special_tokens:
            b_st = st.encode("utf-8")
            self.vocab[current_id] = b_st
            self.token_to_id[b_st] = current_id
            current_id += 1

        # 紧接着存入 0 ~ 255 的基础单字节 (占用 ID 4 ~ 259)
        for b in range(256):
            b_byte = bytes([b])
            self.vocab[current_id] = b_byte
            self.token_to_id[b_byte] = current_id
            current_id += 1

Upon executing this logic, the tokenizer launches with 260 fundamental vocabulary entries (4 special tokens + 256 byte atoms).

Module 2: Training Core—Finding Max-Frequency Pairs & Merging

Training a tokenizer is the iterative process of scanning the entire corpus repeatedly to discover and merge the highest-frequency pairs:

    def train(self, texts: List[str], target_vocab_size: int = 4096, verbose: bool = True):
        # 第一步：预分词。把所有句子切成块，并转为基础字节的数字列表
        words = []
        for text in texts:
            for match in self.SPLIT_REGEX.finditer(text):
                chunk = match.group()
                # 将切块编码成字节，并查表转为初始 ID 列表
                token_ids = [self.token_to_id[bytes([b])] for b in chunk.encode("utf-8")]
                if token_ids:
                    words.append(token_ids)

        # 第二步：迭代合并。需要合并的次数 = 目标词表大小 - 当前已有大小
        num_merges = target_vocab_size - self.vocab_size
        for step in range(num_merges):
            pair_counts: Dict[Tuple[int, int], int] = {}
            # 扫描所有单词，统计相邻 pair 出现次数
            for word in words:
                for i in range(len(word) - 1):
                    pair = (word[i], word[i + 1])
                    pair_counts[pair] = pair_counts.get(pair, 0) + 1

            if not pair_counts:
                break # 没有可合并的了，提前结束

            # 找出出现次数最多的冠军 Pair
            best_pair = max(pair_counts, key=pair_counts.get)
            if pair_counts[best_pair] < 2:
                break # 如果最高频的 pair 才出现 1 次，合并毫无价值，停机

            # 产生新 Token 并注册到字典
            new_id = self.vocab_size
            self.merges[best_pair] = new_id
            new_bytes = self.vocab[best_pair[0]] + self.vocab[best_pair[1]]
            self.vocab[new_id] = new_bytes
            self.token_to_id[new_bytes] = new_id

            # 就地替换：在原数据集中把所有的 best_pair 替换为 new_id
            new_words = []
            for word in words:
                i = 0
                new_word = []
                while i < len(word):
                    if i < len(word) - 1 and (word[i], word[i + 1]) == best_pair:
                        new_word.append(new_id)
                        i += 2 # 跨越两位
                    else:
                        new_word.append(word[i])
                        i += 1
                new_words.append(new_word)
            words = new_words

Module 3: Encoding (Encode) and Decoding (Decode)

Encoding: Text $\to$ Numbers

When a user inputs a text sentence, how does the tokenizer apply its learned rules?

    def encode(self, text: str, add_bos: bool = False, add_eos: bool = False) -> List[int]:
        result = []
        if add_bos:
            result.append(self.bos_token_id) # 句子开头加上 <s>

        for match in self.SPLIT_REGEX.finditer(text):
            chunk = match.group()
            # 1. 拆成单字节 ID
            chunk_ids = [self.token_to_id[bytes([b])] for b in chunk.encode("utf-8")]
            # 2. 按照学到的合并规则逐级合并
            merged_ids = self._merge_token_sequence(chunk_ids)
            result.extend(merged_ids)

        if add_eos:
            result.append(self.eos_token_id) # 句子末尾加上 </s>

        return result

Decoding: Numbers $\to$ Text

Decoding is the exact inverse of encoding: look up token IDs to retrieve raw bytes, concatenate them, and decode into a UTF-8 string:

    def decode(self, token_ids: List[int], skip_special_tokens: bool = True) -> str:
        byte_chunks = []
        for tid in token_ids:
            # 忽略掉 <s>, </s>, <pad> 等控制符号
            if skip_special_tokens and tid in [self.pad_token_id, self.bos_token_id, self.eos_token_id, self.unk_token_id]:
                continue
            if tid in self.vocab:
                byte_chunks.append(self.vocab[tid])

        # 核心：将所有散落的字节拼成完整的 bytes 数组，再反解出汉字与 Emoji
        all_bytes = b"".join(byte_chunks)
        return all_bytes.decode("utf-8", errors="replace")

1.5 Industrial Evolution: Pre-tokenization Boundary Traps & Fused Punctuation

When deploying LLMs in high-density symbolic domains (such as classical poetry, source code, and mathematics), engineers encounter a subtle and destructive architectural trap: punctuation probability bias and isolated character oscillations.

1.5.1 The Subtle GPT-2 Regex Boundary Trap in Chinese

The classic GPT-2 / GPT-4 pre-tokenization regular expression is defined as follows:

SPLIT_REGEX = re.compile(r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

• ?\p{L}+: Slices consecutive alphabetic letters and Chinese characters into word chunks;
• ?[^\s\p{L}\p{N}]+: Forcefully slices punctuation marks into isolated chunks!

Disaster Ensues: When processing the verse "床前明月光，疑是地上霜。", the tokenizer slices the text into: ["床前明月光", "，", "疑是地上霜", "。"]

Because BPE merges can never cross chunk boundaries, this implies: Regardless of how massive your training corpus is or how many iterations BPE runs, Chinese characters and trailing punctuation can never be merged into a single token!

During autoregressive sampling, because commas and periods account for over 12.5% of classical poetic corpora, generating a single character immediately subjects the model to disproportionately high punctuation attractor probabilities, triggering repetitive rhythm collapse!

1.5.2 The Solution: Fused Punctuation Regex

The most elegant engineering resolution is fine-tuning the pre-tokenization regex, permitting Chinese clauses to greedily absorb their trailing punctuation mark:

# 标点吸附正则：允许汉字词块末尾吸收一个中文标点（，。！？；）
SPLIT_REGEX = re.compile(
    r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+(?:[，。！？；])?| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""
)

1.5.3 Three Game-Changing Engineering Benefits

• Completely Eliminates Punctuation Attraction (Isolated punctuation plummets by 93%):

Across our 460k classical poem corpus, Fused Punctuation with a 4096 vocabulary reduced isolated punctuation tokens from 13.11% down to just 0.92%, totally extinguishing metrical sampling stalls!

• Accelerates Training and Inference by 15%~20%:

A standard 28-character seven-syllable quatrain previously demanded 32 tokens; after fusion, it compresses to exactly 28 tokens, conserving context window and boosting training throughput.

• Perfect Alignment with 0.04B Parameter Budget:

A 4096 vocabulary requires only $4096 \times 512 \approx 2.10\text{M}$ embedding parameters (only 5.5% of model capacity), leaving 94.5% of weights for deep attention and SwiGLU layers.

1.6 Industrial Evolution: Structured Special Tokens & Atomic Split Protection (Troubleshooting Clinic 1)

In production LLM systems, alongside natural language text, we must guide the model to comprehend system structural boundaries (such as sequence starts, padding, metadata markers). This requires special tokens.

1.6.1 Architectural Definition of Special Tokens

For our 0.04B Mini-LLaMA architecture, we reserve 8 dedicated special tokens:

DEFAULT_SPECIAL_TOKENS = [
    "<pad>",         # ID 0: 批次填充占位符
    "<s>",           # ID 1: 文本起始符 (BOS)
    "</s>",          # ID 2: 文本结束符 (EOS)
    "<unk>",         # ID 3: 未知字符标记 (Byte-Level 下作为冗余占位)
    "<|title|>",     # ID 4: 诗词题目引导标记
    "<|author|>",    # ID 5: 作者姓名引导标记
    "<|dynasty|>",   # ID 6: 朝代归属引导标记
    "<|content|>"    # ID 7: 诗词正文起始标记
]

Following these 8 special tokens are the 256 fundamental byte atoms (IDs 8 ~ 263), followed by BPE merged subword tokens (IDs 264 ~ 4095).

1.6.2 Troubleshooting Clinic 1: Special Token BPE Split Trap

When beginners implement custom tokenizers, the most common subtle blunder is:

“We declared <|title|> in the vocabulary, but calling encode('<|title|>') emits a string of subword IDs!”

Fatal Root Cause: Pre-tokenization Regex Penetration

Recall our regex SPLIT_REGEX: it slices text into letters, words, and punctuation symbols.

When passing <|title|> into the tokenizer:

• <| is sliced as non-word symbols;
• title is sliced as an English word;
• |> is sliced as non-word symbols.

The consequence: Before your special token ever reaches BPE merge logic, the regex forcibly shreds it into 3 separate fragments!

The model never sees your intended ID 4 (<|title|>), receiving instead disjointed ASCII fragments, causing conditional pretraining loss masking to fail completely.

Industrial Solution: Atomic Split Protection

The fix is brilliant: before sending text to SPLIT_REGEX, apply a dedicated regex compiled from special tokens to split the stream into "special tokens" and "normal text":

def _update_special_pattern(self):
    """按长度降序贪婪编译特殊标记正则"""
    if self.special_tokens:
        sorted_tokens = sorted(self.special_tokens, key=len, reverse=True)
        pattern_str = "(" + "|".join(re.escape(st) for st in sorted_tokens) + ")"
        self.special_token_pattern = re.compile(pattern_str)

Enforcing atomic protection within encode():

if allowed_special and self.special_token_pattern:
    parts = self.special_token_pattern.split(text)
    for part in parts:
        if not part:
            continue
        # 命中特殊标记：直接转为对应单一原子 ID，严禁拆散！
        if part in self.special_tokens:
            result.append(self.token_to_id[part.encode("utf-8")])
        else:
            # 普通文本才送进 SPLIT_REGEX 走常规 BPE 切分
            self._encode_chunk(part, result)

Through this protective gate, no matter how complex the prompt is, special tokens are delivered into the neural network as inviolable atomic units, providing rock-solid foundations for conditional pretraining.

1.7 Hands-on Verification: Validating Your Tokenizer

Now run the complete unit test in your terminal:

python tests/test_tokenizer.py

Console Output Live Preview:

初始词表大小（含特殊标记与基础 256 字节）: 264
[Tokenizer] 开始训练 BPE，初始词表大小: 264，目标词表大小: 320
[Tokenizer] 训练完成！最终词表大小: 276

--- 编解码结果 ---
原始文本: 从零手搓 Transformer 🚀 与 Tokenizer！
Token IDs: [1, 236, 195, 150, ..., 247, 196, 137, 2]
解码还原: 从零手搓 Transformer 🚀 与 Tokenizer！

--- 特殊 Token 原子提取与结构化元数据测试 ---
元数据序列: <|title|>登鹳雀楼<|author|>王之涣<|dynasty|>唐<|content|>白日依山尽，黄河入海流。</s>
元数据 Token IDs: [4, 239, 161, 195, 241, 193, 187, 241, 163, 136]...
跳过特殊标记还原: 登鹳雀楼王之涣唐白日依山尽，黄河入海流。

✅ Tokenizer 纯原生无损编解码与特殊 Token 原子保护校验 100% 通过！

Behold! Complex Chinese verses and English words are cleanly encoded and decoded, and even 4-byte rocket emojis 🚀 and all 8 structured special tokens maintain 100% round-trip fidelity!

1.8 Mentor Summary and Practice Exercises

Through this guide, you have not only learned to use tokenizers, but mastered every internal byte mechanism:

• UTF-8 Variable Length Bytes: The physical bedrock of universal zero-OOV encoding;
• 256 Atomic Bytes: The absolute guarantee that an LLM will never encounter <UNK> crashes;
• Fused Punctuation Regex: Solves the 13% punctuation attraction crisis in classical verse, slashing isolated punctuation oscillations by 93%;
• Special Token Atomic Protection: Establishes lossless structural metadata communication with the neural network.

💡 Hands-on Lab Experiment

Execute the following in your Python terminal:

tok = ByteBpeTokenizer.load("data/tokenizer.json")
ids = tok.encode("<|title|>静夜思<|author|>李白<|content|>床前明月光")
print("第 0 个 ID:", ids[0])  # 看看是否等于 4 (<|title|>)？

Reflect on this: If _update_special_pattern is removed, how many token IDs would <|title|> decompose into?

With the keys forged and numerical sequences prepared, in the next chapter we step into the central computing cortex of modern LLMs: Chapter 02 ｜ Implementing Modern Transformer Architecture from Scratch.