Implementing BPE and SentencePiece Tokenizers from Scratch: A Complete Educational Guide

The ai-engineering-from-scratch repository provides a complete educational implementation of Byte-Pair Encoding (BPE) with extensible architecture for SentencePiece, allowing developers to understand sub-word tokenization by building it from first principles rather than relying on black-box libraries.

The rohitg00/ai-engineering-from-scratch repository offers a hands-on curriculum for understanding modern Large Language Model internals, with a specific focus on implementing BPE and SentencePiece tokenizers from scratch. This educational codebase demonstrates how sub-word tokenization works at the byte level, providing production-quality reference implementations that bridge the gap between academic papers and practical AI engineering.

Architectural Overview of the BPE Implementation

The core tokenization logic resides in phases/10-llms-from-scratch/01-tokenizers/code/bpe.py, which defines the BPETokenizer class. This implementation follows the classic algorithm described in Sennrich et al., 2016, the seminal paper that adapted 1994 compression techniques for modern NLP.

Core Components

The BPETokenizer class encapsulates the full tokenization pipeline through several key methods:

• train(corpus, num_merges) – Builds the vocabulary by iteratively merging the most frequent adjacent byte pairs
• encode(text) – Applies learned merges to convert raw text into token IDs
• decode(ids) – Reconstructs the original text from token IDs using the vocabulary
• _get_pairs(token_list) – Counts frequencies of adjacent token pairs using Python's Counter
• _merge_pair(pair, token_list) – Executes a single merge operation, replacing all occurrences of a specific pair with a new token ID

The implementation initializes with a 256-byte base vocabulary representing all possible byte values, then grows the vocabulary to 256 + num_merges through greedy compression.

How the BPE Tokenizer Works Step-by-Step

The algorithm implemented in bpe.py follows a precise seven-stage pipeline:

1. Initialize – The vocabulary starts with 256 entries, each representing one possible byte value (0-255).

2. Pair Counting – The _get_pairs method builds a frequency distribution of all adjacent token pairs in the current token list.

3. Merge Selection – The system identifies the most frequent pair using max(pairs, key=pairs.get) and designates it as best_pair.

4. Merge Execution – _merge_pair replaces every occurrence of best_pair with a new token ID calculated as 256 + i (where i is the current merge iteration). The new token's byte string is stored in self.vocab.

5. Repeat – Steps 2-4 execute for num_merges iterations, progressively building larger sub-word units from frequent byte combinations.

6. Encoding – The encode method applies the learned merges to new input text, processing the byte sequence iteratively until no more merges are possible.

7. Decoding – The decode method concatenates stored byte strings and decodes them back to UTF-8, using "replace" error handling for invalid sequences.

SentencePiece Concepts and Extension Points

While the repository provides a complete BPE implementation, it also lays the groundwork for SentencePiece tokenization through conceptual documentation in phases/10-llms-from-scratch/01-tokenizers/docs/en.md.

Raw Unicode Processing

Unlike traditional tokenizers that require pre-tokenization (splitting on whitespace and punctuation), SentencePiece operates directly on raw UTF-8 byte streams. This language-agnostic approach eliminates the need for language-specific pre-tokenization regex patterns.

BPE Mode vs Unigram Mode

The documentation describes two operational modes:

• BPE Mode – Identical to the implemented BPETokenizer, but without the pre-tokenization step, operating directly on byte sequences.
• Unigram Mode – The reverse of BPE: starting with a large initial vocabulary and iteratively removing tokens that contribute least to the overall likelihood of the training corpus.

Extending to Unigram Tokenization

The lesson documentation provides a mathematical sketch for converting the BPE training loop into a unigram-pruning loop. After computing token frequencies, developers calculate a likelihood ratio for each token and drop the lowest-scoring tokens until reaching the target vocabulary size. While the repository does not ship a complete unigram implementation, the existing BPETokenizer architecture provides the foundation for this extension.

Practical Implementation and Code Examples

The bpe.py file includes runnable demo functions that demonstrate real-world usage.

Training a Custom BPE Tokenizer

from bpe import BPETokenizer

corpus = (
    "The cat sat on the mat. The cat ate the rat. "
    "The dog sat on the log. The dog ate the frog."
)

tokenizer = BPETokenizer()
tokenizer.train(corpus, num_merges=30)

print("Vocab size after training:", tokenizer.vocab_size())

# → Vocab size after training: 286

Encoding and Decoding Text

sentence = "The cat sat on the mat."
ids = tokenizer.encode(sentence)

print("Encoded IDs:", ids)

# → Encoded IDs: [84, 104, 101, 32, 99, 97, 116, 32, 115, 97, 116, 32, 111, 110, 32, 116, 104, 101, 32, 109, 97, 116, 46]

decoded = tokenizer.decode(ids)
print("Round-trip correct:", decoded == sentence)

# → Round-trip correct: True

Comparing with Production Tokenizers

The repository includes a demo_tiktoken() function that compares the educational implementation against OpenAI's production-grade tiktoken library:

try:
    import tiktoken
    enc = tiktoken.get_encoding("cl100k_base")
    print("tiktoken token count:", len(enc.encode(sentence)))
except ImportError:
    print("Install tiktoken: pip install tiktoken")

Testing and Validation Strategy

The curriculum enforces correctness through comprehensive unit tests located in phases/19-capstone-projects/30-bpe-tokenizer-from-scratch/code/tests/test_bpe.py. These tests verify:

• Round-trip correctness – Ensuring decode(encode(text)) returns the original input
• Merge ordering – Validating that merges occur in descending frequency order
• Special token handling – Managing control tokens and byte-fallback mechanisms
• Deterministic encoding – Guaranteeing identical inputs produce identical token sequences

The test suite serves as a reference specification for extending the base implementation toward full SentencePiece compatibility.

Summary

• The ai-engineering-from-scratch repository provides a complete, educational implementation of BPE tokenization suitable for production understanding.
• Core implementation resides in phases/10-llms-from-scratch/01-tokenizers/code/bpe.py, featuring the BPETokenizer class with methods train, encode, and decode.
• Algorithm foundation follows Sennrich et al., 2016, starting with a 256-byte vocabulary and performing greedy merge operations.
• SentencePiece architecture is conceptually documented for both BPE and Unigram modes, providing extension pathways for raw UTF-8 processing.
• Validation suite in phases/19-capstone-projects/30-bpe-tokenizer-from-scratch/code/tests/test_bpe.py ensures implementation correctness through automated testing.

Frequently Asked Questions

What is the difference between the BPE implementation and SentencePiece in this repository?

The repository provides a complete, runnable BPE implementation in bpe.py that follows the standard byte-pair merging algorithm. SentencePiece coverage is currently conceptual: the documentation in phases/10-llms-from-scratch/01-tokenizers/docs/en.md explains how SentencePiece operates on raw Unicode without pre-tokenization and describes the Unigram algorithm's token pruning strategy. The existing BPE code provides the foundation for building a full SentencePiece tokenizer, but the unigram mode requires additional implementation of the likelihood-based pruning loop.

How does the tokenizer handle unknown characters or languages?

The implementation uses byte-level fallback as its foundation. Since the vocabulary starts with all 256 possible byte values, the tokenizer can represent any UTF-8 sequence, including rare characters, emojis, or non-Latin scripts, by decomposing them into bytes. This approach guarantees that the tokenizer will never encounter an "unknown" character—it simply represents unfamiliar Unicode points as sequences of byte tokens, maintaining the ability to encode any valid UTF-8 text.

Can I use this tokenizer for training a real Large Language Model?

While the educational implementation demonstrates correct algorithmic behavior, production LLMs typically use optimized libraries like tiktoken, Hugging Face Tokenizers, or Google SentencePiece for performance reasons. However, the BPETokenizer class produces compatible tokenization results and can serve as a reference implementation for understanding vocabulary construction, merge rules, and encoding logic. For production use, consider this codebase a learning tool and specification reference rather than a high-performance replacement.

Where are the unit tests for verifying tokenizer correctness?

The comprehensive test suite resides in phases/19-capstone-projects/30-bpe-tokenizer-from-scratch/code/tests/test_bpe.py. These tests validate round-trip encoding/decoding, correct merge ordering by frequency, and proper handling of edge cases. The tests are designed to verify that your implementation matches the expected behavior of standard BPE algorithms, making them essential for anyone extending the code toward SentencePiece functionality or modifying the core tokenization logic.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}