Byte-Pair Encoding (BPE) and Modern Subword Tokenization: Mathematical Foundations, Merge Dynamics, Byte-Level Encodings, and Vocabulary Compression Mechanics

Tokenization is the discrete boundary interface between raw textual sequences and the continuous vector representations of autoregressive large language models. Before an attention block computes a single inner product or a feed-forward network applies an activation function, an input string must be mapped into an ordered sequence of discrete integer identifiers drawn from a finite vocabulary $V$.

The design and mathematical properties of this mapping govern key operational characteristics of large language models: context window efficiency, arithmetic reasoning fidelity, multilingual parity, and inference throughput.

1. The Subword Objective and Vocabulary Trade-offs

A tokenization algorithm maps an arbitrary string of characters or bytes $S = (c_1, c_2, \dots, c_N)$ into a sequence of discrete tokens $T = (t_1, t_2, \dots, t_M)$, where each $t_j \in V$ and $M \le N$.

The tokenization design space presents two boundary extremes, both of which impose unacceptable computational penalties for autoregressive transformer architectures:

1. Word-Level Tokenization:

• In word-level tokenization, the vocabulary $V$ consists of full words separated by whitespace or punctuation.
• Failure Modes: Natural language vocabularies follow Zipfian distributions with heavy tails. Morphological variations, compounding, typos, and domain-specific terminology yield an unbounded vocabulary ($|V| \to \infty$). Any token outside the fixed vocabulary must map to an unknown symbol (<unk>), causing catastrophic information loss. Furthermore, the embedding matrix size $|V| \times d_{\text{model}}$ and the final classification head scale linearly with $|V|$, consuming excessive GPU memory.

1. Character-Level Tokenization:

• In character-level tokenization, $V$ contains only base characters ($|V| \approx 10^2 \text{ to } 10^3$).
• Failure Modes: While <unk> tokens are minimized, the sequence length $M$ expands dramatically. Because standard multi-head self-attention scales quadratically with sequence length ($\mathcal{O}(M^2)$ compute and KV-cache memory), character-level modeling imposes severe latency and throughput bottlenecks. In addition, individual characters carry minimal semantic density, forcing lower transformer layers to spend parameter capacity constructing basic morphemes.

The Subword Optimization Goal

Subword tokenization balances these extremes. It constructs a vocabulary $V$ of variable-length character or byte sequences such that frequent words are represented as single atomic tokens, while rare words are broken down into transparent subword components.

The formal optimization objective of subword vocabulary construction is to minimize the expected sequence length $\mathbb{E}[M]$ (or equivalently, maximize compression) across a representative training corpus $\mathcal{C}$ under a strict upper bound on the vocabulary size $|V| \le V_{\text{target}}$:

$$\min_{V, \, |V| \le V_{\text{target}}} \; \sum_{S \in \mathcal{C}} |T(S; V)|$$

where $T(S; V)$ denotes the sequence of tokens generated by segmenting string $S$ using vocabulary $V$.

2. Classic Byte-Pair Encoding (BPE)

Originally introduced by Philip Gage (1994) as a lossless data compression technique, Byte-Pair Encoding was adapted to neural natural language processing by Sennrich, Haddow, and Birch (2015) for subword translation.

BPE Vocabulary Construction Algorithm

BPE builds a vocabulary bottom-up through greedy iterative pair replacement.

1. Initialization:

• Given a pre-segmented training corpus $\mathcal{C}$ where words are split into sequences of individual characters followed by an end-of-word marker (such as </w>), the initial vocabulary $V_0$ is set to the set of all unique base characters present in $\mathcal{C}$:

$$V_0 = \{c \mid c \in \mathcal{C}\}$$

1. Frequency Counting:

• At iteration $k$, the algorithm computes the co-occurrence frequency of every adjacent symbol pair $(u, v)$ across all tokenized words in $\mathcal{C}$:

$$c(u, v) = \sum_{w \in \mathcal{C}} \text{count}_w(u, v) \times \text{freq}(w)$$

1. Greedy Merge:

• The symbol pair with the highest co-occurrence frequency is selected:

$$(u^<em>, v^</em>) = \arg\max_{(u, v) \in V_k \times V_k} c(u, v)$$

• A new composite symbol $w^* = u^* \circ v^*$ is instantiated and appended to the vocabulary:

$$V_{k+1} = V_k \cup \{w^*\}$$

1. Corpus Update:

• Every contiguous occurrence of the sequence $(u^, v^)$ in the corpus representation is replaced with the merged symbol $w^*$.

1. Termination:

• Steps 2 through 4 repeat until $|V| = V_{\text{target}}$ or the maximum pair frequency drops below a predefined threshold. The sequence of selected merges forms an ordered merge table:

$$\mathcal{M} = \big( (u_1, v_1) \to w_1, \, (u_2, v_2) \to w_2, \, \dots, \, (u_K, v_K) \to w_K \big)$$

Deterministic Inference Tokenization

During inference, tokenizing an unseen string $S$ involves applying the ordered merge table $\mathcal{M}$:

1. Split the string into its constituent base characters: $T_0 = (c_1, c_2, \dots, c_N)$.
2. Iterate through the merge table $\mathcal{M}$ in ascending order of merge rank $r \in \{1, \dots, K\}$.
3. For merge rule $(u_r, v_r) \to w_r$, scan $T$ and replace all adjacent matches of $(u_r, v_r)$ with $w_r$.
4. Return the final token sequence once no remaining merge rules apply.

Because merge rules are applied according to their training creation rank, the tokenization is deterministic.

3. Comparison with WordPiece and Unigram Language Model Tokenization

While BPE dominates modern open-weight and proprietary architectures, two alternative subword paradigms are widely deployed across language modeling: WordPiece and Unigram LM.

WordPiece

Developed by Schuster and Nakajima (2012) and utilized in BERT (Devlin et al., 2018), WordPiece also employs a bottom-up merge strategy but replaces raw frequency ranking with a likelihood maximization criterion.

At each merge step, WordPiece evaluates candidate symbol pairs $(u, v)$ using the ratio of their joint probability to the product of their individual marginal probabilities:

$$\text{Score}(u, v) = \frac{p(u, v)}{p(u) \, p(v)} = \frac{\text{count}(u, v) \times |\mathcal{C}|}{\text{count}(u) \times \text{count}(v)}$$

This scoring mechanism penalizes pairs composed of highly frequent individual characters unless they appear together with disproportionate frequency, favoring merges that maximize the mutual information between subwords.

Unigram Language Model Tokenization

Introduced by Taku Kudo (2018) and implemented in SentencePiece (Kudo & Richardson, 2018), the Unigram tokenization algorithm reverses the direction of vocabulary generation: it starts with an oversized candidate vocabulary and iteratively prunes suboptimal tokens.

+-----------------------------------------------------------------------------+
|                     SUBWORD TOKENIZATION PARADIGMS                          |
+---------------------+-----------------------+-------------------------------+
| Algorithm           | Direction             | Selection Metric              |
+---------------------+-----------------------+-------------------------------+
| BPE                 | Bottom-Up (Agglomerative) | Raw Pair Frequency: count(u, v)   |
| WordPiece           | Bottom-Up (Agglomerative) | Likelihood Ratio: p(uv)/(p(u)p(v))|
| Unigram LM          | Top-Down (Pruning)    | Marginal Loss / Relative Entropy|
+---------------------+-----------------------+-------------------------------+

The Unigram algorithm operates as follows:

1. Vocabulary Initialization:

• Construct a large seed vocabulary $V_{\text{init}}$ containing all single characters and frequent substrings extracted from corpus $\mathcal{C}$ ($|V_{\text{init}}| \gg V_{\text{target}}$, typically $10^5 \text{ to } 10^6$ entries).

1. Expectation-Maximization Optimization:

• Assume a unigram language model where the probability of a token sequence $\mathbf{x} = (x_1, \dots, x_M)$ is the product of independent token probabilities:

$$P(\mathbf{x}) = \prod_{j=1}^M p(x_j), \quad \sum_{x \in V} p(x) = 1$$

• For a given sentence $X$, multiple valid segmentations $S(X)$ exist. The marginal likelihood of the corpus $\mathcal{C} = (X_1, \dots, X_U)$ is:

$$\mathcal{L} = \sum_{i=1}^U \log P(X_i) = \sum_{i=1}^U \log \left( \sum_{\mathbf{x} \in S(X_i)} \prod_{x_j \in \mathbf{x}} p(x_j) \right)$$

• The token probabilities $p(x)$ are estimated iteratively using the Expectation-Maximization (EM) algorithm, where the E-step computes expected token occurrences across the lattice using the Forward-Backward algorithm, and the M-step updates token probabilities.

1. Marginal Loss Pruning:

• For each token $x \in V$, compute the loss increase $\Delta \mathcal{L}_x = \mathcal{L}_{V \setminus \{x\}} - \mathcal{L}_V$ incurred if $x$ were removed from the vocabulary.
• Sort tokens by $\Delta \mathcal{L}_x$ and discard the bottom $10\% \text{ to } 20\%$ of tokens with the lowest marginal impact on likelihood.
• Re-estimate $p(x)$ and repeat until $|V| = V_{\text{target}}$.

1. Viterbi Inference and Subword Regularization:

• To segment a string $X$ at inference time, Unigram computes the optimal segmentation using the Viterbi algorithm over the token lattice:

$$\mathbf{x}^* = \arg\max_{\mathbf{x} \in S(X)} \sum_{x_j \in \mathbf{x}} \log p(x_j)$$

• Subword Regularization: During training, rather than selecting the single Viterbi path, one can sample segmentations from $S(X)$ according to their posterior distribution $P(\mathbf{x} \mid X) = \frac{P(\mathbf{x})}{\sum_{\mathbf{x}' \in S(X)} P(\mathbf{x}')}$, exposing the neural model to varied subword segmentations and improving generalization on noisy inputs.

4. Byte-Level BPE (BBPE) and the Elimination of Out-of-Vocabulary Tokens

Early subword tokenizers operated on Unicode character strings. However, Unicode contains over 149,000 defined characters across diverse scripts, emojis, and control symbols. Initializing $V_0$ with all possible Unicode characters results in an unmanageably large base vocabulary before any merges take place. Conversely, restricting $V_0$ to common characters inevitably reintroduces <unk> tokens when rare scripts or emojis appear.

To resolve this limitation, Radford et al. (2019) introduced Byte-Level Byte-Pair Encoding (BBPE) in GPT-2, an architecture subsequently adopted by Llama, Mistral, Qwen, and Tiktoken.

The Byte-Level Foundation

In BBPE, the initial vocabulary $V_0$ is defined over the 256 possible values of an 8-bit byte:

$$V_0 = \{0x00, 0x01, \dots, 0xFF\}$$

Because any text string can be encoded into a valid UTF-8 byte sequence, every possible string, including arbitrary binary data, rare non-Latin scripts, and unseen emojis, can be decomposed into base bytes.

$$\text{Out-of-Vocabulary Probability: } P(\text{token} = \langle\text{unk}\rangle) \equiv 0$$

Byte-to-Unicode Reversible Mapping

Standard string processing engines and regex parsers encounter faults when handling raw control characters (such as null bytes 0x00 or newline control codes) and invalid partial UTF-8 byte sequences.

To circumvent this, BBPE implements an invertible, bijective mapping $f: \{0, \dots, 255\} \to \mathcal{U}_{\text{printable}}$ that translates each of the 256 byte values into a distinct printable Unicode character:

def bytes_to_unicode():
    # Printable ASCII and Latin-1 Supplement ranges
    bs = list(range(ord("!"), ord("~") + 1)) + \
         list(range(ord("¡"), ord("¬") + 1)) + \
         list(range(ord("®"), ord("ÿ") + 1))
    cs = bs[:]
    n = 0
    # Map remaining non-printable bytes to unused Unicode code points
    for b in range(256):
        if b not in bs:
            bs.append(b)
            cs.append(256 + n)
            n += 1
    return dict(zip(bs, [chr(c) for c in cs]))

This mapping guarantees that all byte manipulation occurs within standard string processing pipelines without byte corruption or parser crashes.

5. Pre-Tokenization, Regex Splitting, and Merge Boundary Control

A major failure mode of naive BPE is the formation of cross-boundary merges. Without constraints, a greedy BPE model merges punctuation marks with adjoining words (such as dog., dog,, dog?), capitalization variants (The, the), and numerical strings with text ($100, 100m). This fragments the vocabulary, requiring separate token allocations for identical semantic roots attached to varied punctuation.

To enforce lexical boundaries, modern tokenizers apply a pre-tokenization regular expression that segments raw text into isolated chunks prior to BPE merge evaluations. Merges are strictly forbidden from crossing chunk boundaries.

+-----------------------------------------------------------------------------+
|                     REGEX PRE-SPLITTING WORKFLOW                            |
|                                                                             |
| Raw Input:  "Model weights: $450M in 2026."                                |
|                                                                             |
|   | (Regex Pre-Tokenizer Regex Split)                                       |
|   v                                                                         |
| Chunks:     ['Model', ' weights', ':', ' $', '450', 'M', ' in', ' 2026', '.']|
|                                                                             |
|   | (Isolated BPE Merge Evaluation)                                         |
|   v                                                                         |
| Tokens:     [14923, 7812, 25, 412, 18921, 44, 294, 39182, 13]              |
+-----------------------------------------------------------------------------+

Evolution of Pre-Tokenization Regex Patterns

The pre-tokenization regex has evolved to refine boundary isolation:

1. GPT-2 Pre-Tokenization Regex:

``regex 's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+ ``

• Matches English contractions separately ('s, 't, 're).
• Groups alphabetic character runs (\p{L}+) with optional leading whitespace.
• Groups numerical digit runs (\p{N}+) with optional leading whitespace.
• Isolates punctuation and special characters ([^\s\p{L}\p{N}]+).

1. Llama 3 and GPT-4 Pre-Tokenization Regex:

``regex (?i:'s|'t|'re|'ve|'m|'ll|'d)|[^\r\n\p{L}\p{N}]?+\p{L}+|\p{N}{1,3}| ?[^\s\p{L}\p{N}]++[\r\n]|\s[\r\n]|\s+(?!\S)|\s+ ``

• Introduces case-insensitive contraction handling.
• Constrains number grouping to chunks of 1 to 3 digits (\p{N}{1,3}), preventing large arbitrary integers from consuming distinct vocabulary slots and regularizing arithmetic representations.
• Isolates line breaks (\r\n) to preserve code indentation structure.

6. Downstream Implications for LLM Architecture and Behavior

The structural mechanics of tokenization directly impact downstream model capabilities and failure modes.

1. Arithmetic and Numeric Representation

Autoregressive models perform multi-digit addition and multiplication by operating over discrete tokens. When a tokenizer groups numbers inconsistently (for example, tokenizing 1024 as 10 + 24, but 1025 as 102 + 5), the positional alignment of decimal digits is scrambled. The model cannot learn uniform digit-level column addition weights across layers.

Modern architectures address this by enforcing single-digit or uniform 3-digit tokenization in the pre-tokenization stage, ensuring each digit occupies a consistent structural position:

$$\text{String } "123456" \implies [1, 2, 3, 4, 5, 6] \quad \text{or} \quad [123, 456]$$

2. Multilingual Compression Disparity

Because BPE merge priorities are driven by corpus frequency, languages with extensive representation in the pre-training corpus (predominantly English) achieve high compression ratios ($\approx 3.5 \text{ to } 4.5 \text{ characters per token}$). Low-resource languages and non-Latin scripts (such as Devanagari, Thai, or Arabic) often receive far fewer merge rules, decomposing words into single bytes ($\approx 1.0 \text{ to } 1.5 \text{ characters per token}$).

$$\text{Relative Context Consumption} = \frac{\text{Tokens}_{\text{Target Language}}}{\text{Tokens}_{\text{English}}} \approx 2.5 \times \text{ to } 4.0 \times$$

This disparity inflates inference latency and API serving costs for non-English users while reducing the effective context window length. Modern foundational models mitigate this by expanding vocabulary sizes from $32\text{k}$ (Llama 1/2) to $128\text{k}$ (Llama 3, Mistral) and $152\text{k}$ (Qwen 2.5), dedicating substantial merge capacity to multilingual subwords.

+-----------------------------------------------------------------------------+
|               VOCABULARY SIZE VS. SEQUENCE COMPRESSION                      |
|                                                                             |
| Model Family      | Vocabulary Size | Non-Latin Token Efficiency            |
+-------------------+-----------------+---------------------------------------+
| Llama 2           | 32,000          | Low (~1.2 chars/token on CJK/Indic)   |
| GPT-4 (cl100k)    | 100,256         | Moderate (~2.4 chars/token)           |
| Llama 3           | 128,256         | High (~3.2 chars/token)               |
| Qwen 2.5          | 152,064         | High (~3.5 chars/token across 29 langs)|
+-------------------+-----------------+---------------------------------------+

3. Glitch Tokens and Embedding Anomalies

When a BPE tokenizer is trained on a massive web scrape, rare strings (such as repeated forum usernames, deterministic code patterns, or trailing whitespace combinations) receive dedicated token IDs in $V$.

If these token IDs rarely or never appear during the subsequent pre-training stage of the neural model, their corresponding rows in the input embedding matrix $W_e$ and unembedding matrix $W_u$ receive negligible gradient updates throughout training. As analyzed by Rumbelow and Watkins (2023), prompting the model with these "glitch tokens" (such as SolidGoldMagikarp or Cloneable-Clara) triggers unpredictable attractor states in activation space, leading to hallucinations, infinite loops, or complete refusal.

7. Comparative Architectural Matrix

The following matrix summarizes the algorithmic mechanics, complexity profiles, and operational parameters across the primary subword tokenization schemes:

+--------------------------------------------------------------------------------------------------------------------+
|                                    SUBWORD TOKENIZER ARCHITECTURAL MATRIX                                          |
+----------------------+--------------------+--------------------+-------------------------+-------------------------+
| Feature              | Classic BPE        | Byte-Level BPE     | WordPiece               | Unigram Language Model  |
+----------------------+--------------------+--------------------+-------------------------+-------------------------+
| Base Unit            | Unicode Characters | 256 Raw Bytes      | Unicode Characters      | Large Substring Set     |
| Construction Mode    | Bottom-up Greedy   | Bottom-up Greedy   | Bottom-up Likelihood    | Top-down Pruning (EM)   |
| Selection Metric     | Pair Co-occurrence | Pair Co-occurrence | Mutual Information      | Relative Entropy Loss   |
| Out-of-Vocabulary    | Yes (<unk>)        | No (0% <unk>)      | Yes (<unk>)             | Handled via Byte Fallback|
| Encoding Complexity  | O(N log K)         | O(N log K)         | O(N^2) Longest-Match    | O(N^2) Viterbi Path     |
| Subword Regularize   | No (Deterministic) | No (Deterministic) | No (Deterministic)      | Yes (Lattice Sampling)  |
| Primary Adoptions    | RoBERTa, GPT-2     | Llama 3, Qwen, GPT4| BERT, DistilBERT        | SentencePiece, T5, Gemma|
+----------------------+--------------------+--------------------+-------------------------+-------------------------+

Sources

• Gage, P. (1994). A New Algorithm for Data Compression. The C Users Journal, 12(2), 23-38. Link.
• Sennrich, R., Haddow, B., & Birch, A. (2015). Neural Machine Translation of Rare Words with Subword Units. arXiv:1508.07909.
• Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Technical Report. PDF.
• Schuster, M., & Nakajima, K. (2012). Japanese and Korean Voice Search. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). DOI:10.1109/ICASSP.2012.6289079.
• Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2018). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv:1810.04805.
• Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. arXiv:1804.10959.
• Kudo, T., & Richardson, J. (2018). SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing. arXiv:1808.06221.
• Rumbelow, J., & Watkins, M. (2023). SolidGoldMagikarp (plus prompt generation). LessWrong. Link.