Tokenization Algorithms: Byte-Pair Encoding (BPE), SentencePiece, and Tiktoken

Tokenization is the critical translation boundary between human natural language and numerical tensor representations. A Large Language Model cannot process raw UTF-8 strings directly; it operates exclusively on sequences of discrete integers called Token IDs.

How text is converted into integers dictates:

1. Context Window Efficiency: How much semantic information fits inside a fixed context length (e.g. 8,192 or 128k tokens).
2. Computational Cost: Transformer compute scales quadratically or linearly with sequence length; fewer tokens per document directly slashes inference latency and FLOPs.
3. Multilingual Fairness & Cost: Token-to-word ratios vary dramatically across languages.
4. Security & Prompt Injection Vulnerabilities: Special token handling determines whether untrusted user inputs can hijack internal control flows.

1. The Tokenization Spectrum

Historically, natural language processing evaluated three primary tokenization paradigms:

Modern production LLMs standardly use Byte-Level Subword Tokenization (such as Byte-Pair Encoding in GPT-4, Llama 3, and Tiktoken).

2. Byte-Pair Encoding (BPE) Mechanics

Originally developed as a general data compression algorithm (Gage, 1994), Byte-Pair Encoding (BPE) was adapted for NLP by Sennrich et al. (2015).

A. The Training Phase (Learning Merge Rules)

1. Initialize Vocabulary: Start with a base vocabulary containing all 256 individual byte values ($0\text{x}00$ to $0\text{xFF}$) plus optional special tokens.
2. Tokenize Corpus into Bytes: Represent training corpus as a sequence of byte tokens.
3. Count Adjacent Pairs: Scan the corpus to find the most frequently occurring adjacent pair of tokens $(t_A,t_B)$.
4. Create a Merge Rule: Assign a new integer ID to the merged token $t_{\text{new}}=t_A\circ t_B$, and replace all occurrences of $(t_A,t_B)$ in the corpus with $t_{\text{new}}$.
5. Iterate: Repeat steps 3–4 until the vocabulary reaches the target size $|\mathcal{V}|$ (e.g. 50,000 or 128,000).

B. The Inference Phase (Encoding Text)

Given a learned list of merge pairs ordered by priority (creation timestamp/rank):

1. Convert the input string into a list of initial byte tokens.
2. Iteratively find the adjacent pair with the lowest merge rank (highest training frequency).
3. Merge that pair into its assigned token ID.
4. Continue until no further adjacent pairs exist in the merge table.

3. The Tiktoken Pre-Tokenization Regex

Naive BPE merges characters indiscriminately across punctuation and whitespace, creating pathological tokens like "\n\n\n\n" or merging the period at the end of a sentence with the capital letter of the next sentence (".The").

Modern tokenizers (such as OpenAI's Tiktoken used in GPT-4 and the Llama 3 tokenizer) first split text using a Pre-Tokenization Regular Expression before executing BPE merges within each split chunk:

Breakdown of the Regex Components:

• '(?i:[sdmt]|ll|ve|re): Matches English contractions ('s, 've, 'll, 're, 't).
• [^\r\n\p{L}\p{N}]?+\p{L}+: Matches letters, optionally preceded by a single space or non-alphanumeric character.
• \p{N}{1,3}: Groups numbers into chunks of up to 3 digits (e.g., 123456 $\to$ 123 and 456), preventing token pollution for arbitrary large numbers.
• ?[^\s\p{L}\p{N}]++[\r\n]*: Matches punctuation clusters.
• \s*[\r\n]|\s+(?!\S)|\s+: Isolates newlines and spaces.

4. Complete Byte-Pair Encoding Engine Implementation in TypeScript

Below is a complete, production-grade Byte-Pair Encoding tokenizer implementation featuring byte-level fallbacks, merge training, encoding, and decoding:

5. Multilingual Token Inflation: The "Token Tax"

One of the most consequential considerations in production LLM architecture is Token Inflation across different languages and alphabets.

Because early BPE tokenizers (e.g. GPT-2 with $|\mathcal{V}|=50,257$) were trained predominantly on English corpora:

• English words average $1.3$ tokens per word.
• German words average $2.1$ tokens per word (due to compound words).
• Hindi, Arabic, and Telugu text averaged $6.0-10.0$ tokens per word because individual script characters decomposed into multiple UTF-8 raw byte tokens.

The Solution: Expanding Vocabulary Size ($|\mathcal{V}|$)

Modern models dramatically expanded their vocabulary sizes:

• GPT-4 (cl100k_base): $|\mathcal{V}|=100,000$
• Llama 3: $|\mathcal{V}|=128,256$
• Gemma 2: $|\mathcal{V}|=256,000$

Expanding vocabulary reduces token inflation for non-Latin scripts by over $70\%$, significantly lowering latency and API costs for global users.

6. Special Tokens and Security Vulnerabilities

Special tokens are non-text control symbols inserted into prompts to establish operational boundaries:

The Token Injection Attack Vector

If an application accepts raw user input and passes it directly to a tokenizer configured with allowed_special="all":

The tokenizer converts <|im_end|> directly into the control token ID, closing the user role and escalating privileges to the system prompt.

Production Rule:

Always sanitize input by specifying disallowed_special=() or allowed_special="none" for all end-user prompts. Only the internal orchestration template engine may inject special control tokens.

7. Landmark Arena Capstone

You are now ready to apply these principles by building a fully functional Byte-Pair Encoding Tokenizer from scratch in the Landmark Global Arena:

👉 Launch Chapter 1 Capstone: Build a Byte-Pair Encoding Tokenizer from Scratch