Sort the initial characters by Unicode code point: d, e, i, l, n, o, r, s, t, w. Give them IDs 0 through 9, and assign new tokens IDs from 10 onward. For equal pair counts, compare the left IDs first, then the right IDs; the smaller pair wins.

For example, e + s has IDs (1, 7) and s + t has (7, 8), so e + s wins. The four words and their frequencies come from Algorithm 1 of Sennrich et al.[1]; this example omits their end-of-word symbol and uses the tie-breaking rule above.

1. [1] Rico Sennrich, Barry Haddow, Alexandra Birch, "Neural Machine Translation of Rare Words with Subword Units," ACL, 2016.

Counts include overlapping positions, while replacements do not. In aaa, a + a occurs twice, but only one occurrence can be replaced. Pair frequency can therefore exceed the number of tokens a merge removes.

Let \(f(s)\) be the number of times the token sequence \(s\) occurs in the training data. The frequency of the pair \((a,b)\) is then

where \(|s|\) is the current length of the sequence, \(s_i\) is its \(i\)-th token, and \(\mathbf{1}\) is the indicator function, equal to 1 when its condition holds and 0 otherwise.

The inner sum counts matching positions in one sequence; the outer sum weights that count by the sequence's frequency. Thus the 5 occurrences of low initially contribute 5 to both l + o and o + w.

The dictionary below contains the four rules from §1.1. Each value is (rank, output ID).

def encode_ids(initial_ids, rules):
    sequence = list(initial_ids)
    while len(sequence) >= 2:
        candidates = [
            (rules[pair][0], i, rules[pair][1])
            for i, pair in enumerate(zip(sequence, sequence[1:]))
            if pair in rules
        ]
        if not candidates:
            break
        # Pick the smallest rank, then the leftmost position.
        _, i, output = min(candidates)
        sequence[i:i + 2] = [output]
    return sequence

# Assign IDs 0 through 9 to the initial characters.
alphabet = {char: i for i, char in enumerate("deilnorstw")}
rules = {
    (1, 7): (0, 10),   # e  + s → es
    (10, 8): (1, 11),  # es + t → est
    (3, 5): (2, 12),   # l  + o → lo
    (12, 9): (3, 13),  # lo + w → low
}
initial_ids = [alphabet[char] for char in "lowest"]
print(encode_ids(initial_ids, rules))  # [13, 11] = low | est

The function also works with byte IDs and their merge rules. The code and data archive includes training, decoding, and the experiments in §4.2; it requires only the Python standard library.

Let \(n\) be the number of initial tokens and assume constant-time ID-pair lookup. If \(m\) merges occur, the Python code performs up to \(O(n)\) work per merge to scan candidates and modify the list. Including the first scan gives \(O(n+mn)\). Since \(m\leq n-1\), the worst case is \(O(n^2)\).

With a linked structure for adjacency and a priority queue, each merge creates only a constant number of new candidates. There are \(O(n)\) candidates over the whole run, each costing \(O(\log n)\) to insert or remove. This gives \(O(n\log n)\), assuming constant-time ID-pair lookup and adjacency updates.

For short inputs, array scans can be faster because they avoid the overhead of these structures. tiktoken 0.12.0 uses arrays and cites cache locality on short pieces as its reason[9]. Runtime comparisons should therefore use the piece lengths that the tokenizer actually processes after pre-tokenization (§3.2).

1. [9] OpenAI, "tiktoken: BPE implementation (v0.12.0)," GitHub, 2025.

SentencePiece enables this behavior with byte_fallback[10]. The 256 byte entries count toward the requested vocabulary size, leaving fewer entries for characters and longer strings. Here bytes cover missing characters; in byte-level BPE, bytes are the starting units for learning every merge.

1. [10] Google, "SentencePiece Training Options," SentencePiece Documentation, 2026.

SentencePiece defaults to a custom NFKC-based rule set. Its identity option disables character normalization; whitespace has separate controls[11]. Check those too: collapsing consecutive spaces, for example, loses information even when the characters are otherwise preserved.

1. [9] OpenAI, "tiktoken: BPE implementation (v0.12.0)," GitHub, 2025.
2. [10] Google, "SentencePiece Training Options," SentencePiece Documentation, 2026.
3. [4] Hugging Face, "The tokenization pipeline," Tokenizers Documentation, 2026.
4. [11] Google, "Text Normalization in SentencePiece," SentencePiece Documentation, 2026.

For pair \((a,b)\), let \(C_\ell(a,b)\) count its occurrences in language \(\ell\), and let \(w_\ell\) be that language's training weight. Select the pair with the largest weighted count:

A weight of 2 gives the same counts as including every training sentence in that language twice. The weights stay fixed during training, while the counts change as merges alter the sequences.

The dataset contains 16 training sentences and 8 evaluation sentences per language. The translations have not been professionally checked; the dataset is intended to demonstrate the mechanism.

Let \(B_\ell\) be the total UTF-8 bytes of the training sentences in language \(\ell\), and \(p_\ell\) its target byte share. Each sentence of that language receives the weight \(100000p_\ell/B_\ell\). The shares \(p_\ell\) sum to 1, so the weighted byte total is 100,000 in every condition. The weights are exact Python Fraction values, and no random sampling is involved. The 50% English condition takes the square root of each share in the 80% condition and normalizes the results to sum to 1.

The initial vocabulary is the 256 byte values, and 256 merges are learned. There is no character normalization; merges cannot cross sentence boundaries but can cross spaces within a sentence. Evaluation applies no weights and sums the token counts of the 8 sentences in each language.

Extract the code and data archive and run this command from the extracted directory. It runs the tests and writes the experiment outputs to results/.

python3 code/run_all.py

The inputs are in data/toy_parallel.json, and the table values are in results/multilingual_metrics.csv. The code uses only the Python standard library. Its README is in Japanese; code/bpe_core.py contains the minimal byte-level implementation, and code/minimal_bpe.py also supports characters.

Table 1 reports tokenizers trained on an unbalanced 30-language sample of FineWeb2 and evaluated on the corresponding FLORES+ languages[6]. Both vocabularies have 128,000 entries.

A Gini coefficient closer to 0 means less disparity in token counts across languages. Compression divides the number of sentences by the total token count, so a larger value means shorter token sequences for this fixed evaluation corpus.

1. [6] Negar Foroutan, Clara Meister, Debjit Paul, Joel Niklaus, Sina Ahmadi, Antoine Bosselut, Rico Sennrich, "Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization," ACL, 2026.

Table 2 compares ordinary BPE with two variants: hybrid learns the first half of its merges with ordinary BPE and the second half with PA-BPE; hybrid+window also limits how often the same language can be selected within a window of recent merges[6].

The tokenizers were trained on mC4, and the models on 100 billion FineWeb2 tokens. Evaluation covered 22 languages. These model results use different tokenizer training data and PA-BPE variants from the tokenizer-only comparison in Table 1.

1. [6] Negar Foroutan, Clara Meister, Debjit Paul, Joel Niklaus, Sina Ahmadi, Antoine Bosselut, Rico Sennrich, "Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization," ACL, 2026.

In Hugging Face Tokenizers 0.22.1, BPE with ignore_merges=True and dropout disabled returns the ID directly if the whole pre-tokenized piece is in the vocabulary[12]. With the three rules above, abc succeeds by direct lookup. Add the initial character x and pass xabc as one piece, absent from the vocabulary: merging yields x | ab | c.

tiktoken 0.12.0 also checks whole pieces first. It then finds merge candidates by looking up the concatenated bytes of neighboring tokens in a rank table[9]. That differs from registering only a specific ID pair such as a + bc; the conflict example depends on the explicit pair rules stated in the body.

The downloadable examples reproduce the pair-rule conflict in results/integration_conflicts.json.

1. [12] Hugging Face, "Tokenizers: BPE model (v0.22.1)," GitHub, 2025.
2. [9] OpenAI, "tiktoken: BPE implementation (v0.12.0)," GitHub, 2025.

The added parameters number \(50000\times4096=204800000\). Stored at 2 bytes per element, as in the 16-bit floating-point format BF16, they take \(409600000\) bytes, or 409.6 MB in decimal megabytes. With separate input and output matrices, the total increase is 819.2 MB.

These figures count weights only. Training also needs gradients, optimizer state, and other memory, and actual memory use depends on the training method.

To compute bits per byte (BPB), sum the negative log-likelihood of the evaluation text's token sequence in bits, then divide by the text's UTF-8 byte count. For the same text, a lower BPB means the model assigns a higher probability to its token sequence.

Perplexity exponentiates mean loss per token, so it retains the tokenizer-dependent unit. BPB instead gives the compared token sequences a shared denominator.