Byte-pair encoding: merges, Unicode and artifact contracts

Why tokens are a model contract

A language model predicts integer IDs. The tokenizer decides whether one prediction event represents a byte, a word piece, a whole word or a control marker. A larger vocabulary can shorten sequences, but enlarges the embedding/output space. Tokenization affects context budgets, multilingual coverage, likelihood units and exact checkpoint compatibility; it is not a model that understands morphology.

Bring the character-level baseline from DL041 and Python dictionaries/Counters. We will hand-trace weighted merges, retain a complete byte-BPE trainer, implement ranked encoding and artifact round trips, inspect GPT-2's file conventions and test Unicode, numbers, whitespace and special tokens. A permitted local1–10MB corpus is an optional extension, not a dataset downloaded or trained in this review.

1 · Greedy adjacent-pair training

Start with a sequence of symbols for each training item. Count adjacent pairs, including item multiplicity; choose the most frequent pair with a specified tie rule; replace its nonoverlapping occurrences left-to-right by a new symbol. Repeat while eligible pairs remain and the merge budget permits. Save both vocabulary IDs and ordered merge rules.

The stenographer analogy is useful: frequent letter pairs receive shorthand. It stops being useful when shorthand is mistaken for meaningful roots. BPE can merge qx before un in a corpus where qx repeats more. It has no morpheme objective, and it does not globally minimize compressed length. With overlapping pairs such as aaa, the adjacent count is2 but the left-to-right replacement count is1; “the pair saves exactly its raw count in tokens” is not always true.

Sennrich et al.,2016 §3.2 use character symbols plus an end-of-word marker and aggregate word counts. GPT-style byte BPE changes the base alphabet and preprocessing. The protected teaching lab below uses UTF-8 bytes and document boundaries instead of GPT-2's exact regex partition.

2 · A corrected hand trace

For the original lesson's frequencies low:5, lower:2, newest:2, widest:3, pair (l,o) occurs7 times, (o,w) also7, and (e,s) only5. Therefore (e,s) cannot be the unique highest-frequency first merge. With a lexicographic tie rule (l,o) wins; (lo,w) then has7 occurrences. The paper's printed Algorithm1 has newest:6, not2, which changes the count of (e,s) to9. Do not splice a paper's output into a different corpus.

After merging (l,o) and then (lo,w), the first two weighted sequences are (low,</w>):5 and (low,e,r,</w>):2. Other words are unchanged. Subsequent counts must be recomputed on the new symbols. A literal marker must be distinguished from a reserved boundary symbol in production; here it is an explicitly chosen character-level illustration.

from collections import Counter
 
def weighted_pairs(words):
    counts = Counter()
    for symbols, weight in words.items():
        for pair in zip(symbols, symbols[1:]):
            counts[pair] += weight
    return counts
 
def merge_words(words, pair):
    out = Counter()
    for word, weight in words.items():
        result, i = [], 0
        while i < len(word):
            if i+1 < len(word) and word[i:i+2] == pair:
                result.append(pair[0]+pair[1]); i += 2
            else:
                result.append(word[i]); i += 1
        out[tuple(result)] += weight
    return out
 
words = {tuple(w)+('</w>',): n for w,n in
         [('low',5),('lower',2),('newest',2),('widest',3)]}
c = weighted_pairs(words)
assert c[('l','o')] == 7 and c[('e','s')] == 5
first = min(c, key=lambda pair: (-c[pair], pair))
assert first == ('l','o')
words = merge_words(words, first)
c = weighted_pairs(words)
assert min(c, key=lambda pair: (-c[pair],pair)) == ('lo','w')
print('weighted first merges', first, ('lo','w'))

3 · Copyable byte tokenizer

For documents abab and abac, (a,b) occurs3 times, (b,a) twice and (a,c) once. Merge (97,98) to256: the sequences become [256,256] and [256,97,99]. Never count a synthetic pair between the last byte of one document and the first byte of the next. The following exact previously verified program remains unchanged.

from collections import Counter
 
def merge(tokens, pair, new_id):
    out, i = [], 0
    while i < len(tokens):
        if i+1 < len(tokens) and (tokens[i], tokens[i+1]) == pair:
            out.append(new_id); i += 2
        else:
            out.append(tokens[i]); i += 1
    return out
 
def train(documents, count):
    seqs = [list(doc.encode('utf-8')) for doc in documents]
    vocab = {i: bytes([i]) for i in range(256)}
    rules = []
    for _ in range(count):
        counts = Counter(pair for seq in seqs for pair in zip(seq, seq[1:]))
        if not counts:
            break
        pair = min(counts, key=lambda p: (-counts[p], p))
        if counts[pair] < 2:
            break
        new_id = len(vocab)
        vocab[new_id] = vocab[pair[0]] + vocab[pair[1]]
        rules.append((pair, new_id))
        seqs = [merge(seq, pair, new_id) for seq in seqs]
    return rules, vocab
 
def encode(text, rules):
    ids = list(text.encode('utf-8'))
    for pair, new_id in rules:
        ids = merge(ids, pair, new_id)
    return ids
 
def decode(ids, vocab):
    return b''.join(vocab[i] for i in ids).decode('utf-8')
 
rules, vocab = train(['abab', 'abac'], 4)
assert rules[0] == ((97, 98), 256)
for text in ['', 'abab', 'café', 'తెలుగు 🙂', 'a\n  b']:
    assert decode(encode(text, rules), vocab) == text
assert merge([97,97,97], (97,97), 256) == [256,97]
assert len(encode('abab', rules)) < len('abab'.encode())
assert train(['abab', 'abac'], 4)[0] == rules
print('merge rules', rules, 'vocabulary size', len(vocab))

This trainer stops when the highest pair count is less than2, even if the requested merge count is larger. That is its explicit policy, not every BPE trainer's stopping rule. It trains on a list of documents in memory, so the naive implementation rescans roughly the remaining corpus length for each merge. Weighted repeated-item aggregation reduces redundant scanning; production trainers can maintain pair occurrence indexes and update affected counts. Neither optimization turns all BPE training into a universal constant-time operation.

4 · Encoding ranks, not longest strings

At inference, apply frozen merge ranks, not new frequency counts. The protected encoder replays each training rule in order. For this trainer, every new symbol is formed from earlier IDs; the rank-based implementation below repeatedly chooses the lowest-rank applicable pair and agrees with replay. Greedy longest-match segmentation is a different algorithm. Consider vocabulary pieces ab, bc with rank (b,c) earlier than (a,b): encoding abc chooses [a,bc], while longest-prefix matching would choose [ab,c].

def encode_ranked(text, rules):
    ranks = {pair: (rank,new_id) for rank,(pair,new_id) in enumerate(rules)}
    ids = list(text.encode('utf-8'))
    while len(ids) > 1:
        pairs = set(zip(ids, ids[1:]))
        candidates = pairs & ranks.keys()
        if not candidates:
            break
        pair = min(candidates, key=lambda p: ranks[p][0])
        ids = merge(ids, pair, ranks[pair][1])
    return ids
 
rank_example = [((98,99),256), ((97,98),257)]
assert encode_ranked('abc', rank_example) == [97,256]
training = ['qx '*30, 'unhappiness', 'ababab café café', 'తెలుగు 🙂 తెలుగు 🙂']
rules2, vocab2 = train(training, 30)
for text in training + ['new text', '', 'a\n  b', '12345', ' Hello']:
    assert encode_ranked(text,rules2) == encode(text,rules2)
    assert decode(encode_ranked(text,rules2),vocab2) == text
assert rules2[0][0] == (113,120)  # qx beats a rare morphological boundary
print('ranked encode/replay and frequency-not-morphology controls pass')

For a large merge table, an occurrence-linked priority queue can avoid rescanning every pair each round, but must invalidate stale heap entries after neighboring merges. Preserve order and deterministic tie behavior before optimizing. Freeze normalization and pre-tokenization too: matching ranks with different chunks does not produce the same tokenizer.

5 · GPT-2 vocabulary files and UTF-8

UTF-8 encodes Unicode scalar values into one to four bytes. A byte alphabet has256 values and covers any byte stream; this Python string interface first performs strict UTF-8 encoding, so lone-surrogate strings are outside its accepted contract. Unicode itself is finite, not literally unbounded; a character vocabulary chosen only from a training sample can still encounter unseen characters. Bytes are a useful small complete alphabet, not the only mathematically possible one.

GPT-2 maps byte values bijectively into visible Unicode symbols before BPE, so vocabulary strings do not contain literal control/whitespace bytes. The glyph Ġ denotes the space byte under that mapping; it is not a control token or a universal word-boundary symbol. encoder.json maps visible token strings to IDs. vocab.bpe contains a header and ordered pair lines. Its decoder concatenates byte payloads and then decodes them under its configured error policy.

The source also applies a Unicode-aware regex before merges, distinguishing contractions, letter runs, number runs, punctuation and whitespace. Python's standard re does not implement \p{L}; GPT-2 imports the regex package. A .split() trainer discards whitespace layout but does not make CJK impossible to represent: a space-free sentence can remain one item whose symbols still get segmented. The real problems are changed boundaries, lost whitespace and inefficient/unrepresentative segmentation.

import json, hashlib
 
def visible_bytes():
    bs = list(range(33,127))+list(range(161,173))+list(range(174,256))
    cs = bs.copy(); extra = 0
    for byte in range(256):
        if byte not in bs:
            bs.append(byte); cs.append(256+extra); extra += 1
    return dict(zip(bs,map(chr,cs)))
 
def export_artifact(rules, vocab):
    table = visible_bytes()
    visible = lambda payload: ''.join(table[b] for b in payload)
    encoder_json = json.dumps({visible(v): k for k,v in vocab.items()},
                              ensure_ascii=False, sort_keys=True)
    merge_text = '#version: 0.2\n' + ''.join(
        visible(vocab[a])+' '+visible(vocab[b])+'\n' for (a,b),_ in rules)
    return encoder_json, merge_text
 
def import_artifact(encoder_json, merge_text):
    inverse = {v:k for k,v in visible_bytes().items()}
    encoder = json.loads(encoder_json)
    vocab = {i:bytes(inverse[c] for c in token) for token,i in encoder.items()}
    if set(vocab) != set(range(len(vocab))):
        raise ValueError('IDs must be contiguous')
    lines = merge_text.splitlines()
    if not lines or lines[0] != '#version: 0.2':
        raise ValueError('version header required')
    rules = []
    for line in lines[1:]:
        a,b = line.split(' ')
        pair = (encoder[a],encoder[b]); new = encoder[a+b]
        if pair[0] >= new or pair[1] >= new:
            raise ValueError('this teaching format requires earlier parent IDs')
        rules.append((pair,new))
    return rules,vocab
 
artifact = export_artifact(rules2,vocab2)
r3,v3 = import_artifact(*artifact)
assert r3 == rules2 and v3 == vocab2
assert visible_bytes()[32] == 'Ġ'
assert len(set(visible_bytes().values())) == 256
print('artifact SHA256', hashlib.sha256(('\0'.join(artifact)).encode()).hexdigest())

These are GPT-2-shaped teaching files for this byte vocabulary, not a downloaded GPT-2 tokenizer or full format-compatible replacement: pre-tokenizer rules, special IDs and arbitrary imported model variants remain separate. Save a manifest containing algorithm, source hashes, normalization, chunk boundaries, tie/stopping policy, byte mapping, merge/vocabulary digests and reserved-ID policy. A vocabulary size alone is not sufficient to restore a checkpoint.

6 · Four pathologies and their actual fixes

Rare artifact tokens / glitch tokens. A string such as SolidGoldMagikarp can behave unusually in a model. Tokenizer-training frequency, LM-training frequency, embedding/output learning and prompting all matter; do not infer that an embedding was literally untouched or that every vendor uses a0.001% deletion cutoff. Even output rows for tokens that are never targets can receive softmax gradients. Audit frequencies and behavior on the actual permitted training distribution. Removing or renumbering IDs after LM training breaks the mapping; repair requires an explicit model/tokenizer migration and evaluation, not deleting a row from a JSON file.

Numbers. BPE is deterministic with a fixed pipeline, but surrounding whitespace/pre-tokenization can change segmentation. Neither exact GPT-2 splits nor arithmetic failure follows solely from the string 12345. Meta's Llama3 source uses number chunks of one to three digits, not “always single digits.” Single-digit rules, fixed-length chunks and ordinary BPE are distinct choices. Evaluate numerical tasks and character counting; do not present tokenization as the sole cause of reasoning errors.

Partial Unicode. A token may end inside a multibyte character. Decode the concatenated stream or buffer partial bytes in a streaming decoder. Strict failure and replacement characters are different product policies; errors='replace' is not always appropriate for lossless data. A generated sequence can be invalid UTF-8 even though every valid input round-trips.

Whitespace. Leading spaces, newlines and indentation may change IDs. Do not strip them unnoticed before hashing, tokenization or caching. A lossless text round trip also does not imply ID round trip: multiple token sequences can spell the same bytes, while deterministic encoding chooses one canonical sequence.

# Unknown valid UTF-8 text still encodes, while arbitrary generated bytes may not.
assert decode(encode('新しい🙂',rules2),vocab2) == '新しい🙂'
try:
    decode([255],vocab2)
    raise AssertionError('invalid UTF-8 unexpectedly decoded')
except UnicodeDecodeError:
    pass
# A token ID sequence can decode identically yet not be the canonical encoding.
assert decode([97,98],vocab) == decode([256],vocab) == 'ab'
assert encode(decode([97,98],vocab),rules) != [97,98]
 
SPECIAL_ID = 1000000
# Only a trusted framing function inserts a structural ID; literal user text stays bytes.
def frame_user(text):
    return [SPECIAL_ID] + encode(text,rules2)
assert SPECIAL_ID not in encode('<|endoftext|>',rules2)
assert frame_user('<|endoftext|>')[0] == SPECIAL_ID
print('UTF-8, noncanonical ID roundtrip and structural-token isolation controls pass')

The framing example is a policy model, not a universal chat template. Production APIs must explicitly choose whether special spellings are allowed, rejected or treated as ordinary text. Blindly removing strings can corrupt legitimate code/documentation and does not solve broader prompt injection.

7 · Vocabulary budgets and current model examples

At width d, a tied input/output token matrix stores Vd weights; untied input and output store about2Vd. Doubling V doubles those weights but does not necessarily halve encoded length, latency or cost. Attention work depends on sequence length; vocabulary projection work increases with V; larger vocabularies leave a longer low-frequency tail. Measure bytes/token, characters/token, tokens per representative document, tail frequencies and downstream quality at matched compute.

Examples must retain model identity and metric denominator. GPT-2 has a roughly50k BPE vocabulary; Llama1/2 use SentencePiece BPE, while Llama3 uses a tiktoken-style128k BPE vocabulary. DeepSeek-V3 reports128k byte-level BPE with tokenizer changes; a claimed universal30% Chinese advantage over another tokenizer is not established by that vocabulary size. Gemma3 uses a large SentencePiece vocabulary, but the original 256k*2048 ≈500M was a hypothetical-width calculation incorrectly attributed to its1B configuration. Gemma3's primary Table1 reports302M embedding parameters and698M non-embedding parameters for its1B model, about30.2% rather than half. Its tokenizer section says262k entries while Table1 uses the shorthand256k; keep the source's conventions visible rather than silently treating them as identical exact counts. For any model, read its actual hidden size and tie policy; do not transfer one variant's dimensions across the family.

Mistral's July2024 NeMo announcement attributes about30% better compression for certain languages/code to Tekken relative to its previous SentencePiece tokenizer, not a blanket30% over Llama3. It separately says Tekken compresses better than Llama3 on about85% of the languages evaluated. Compression percentages are not automatically equivalent inference savings.

TokenMonster is an alternative vocabulary/segmentation system with its own optimization modes and reported benchmarks. Its README describes an “ungreedy” tokenizer; that is not sufficient evidence to relabel its objective a neural LM likelihood or assert a universal5–15% win. Scaling Laws with Vocabulary explicitly studies vocabulary allocation; it is a fitted experimental result, not “larger is always better.”

For a new small model, compare a small domain vocabulary, a larger multilingual vocabulary and a compatible inherited tokenizer on the same held-out text. Inheriting avoids tokenizer engineering but inherits domain coverage and licensing constraints. Retokenizing a pretrained model is a much larger intervention than choosing a vocabulary before pretraining.

8 · Local corpus experiment, exercises and answers

The full optional experiment is: obtain an already-permitted local text file; record its hash and encoding; split by document/group before fitting; train on the training subset only; save artifacts; encode fixed held-out samples under every merge budget; report train/held-out bytes-per-token, elapsed time, peak memory and round-trip failures. Use the same normalization/boundary policy at500,2000 and5000 merges. The naive trainer can be slow on10MB; start with a bounded slice, estimate cost and stop rather than claim a universal two-hour budget or GPT-2 parity within10%.

def compression_report(documents, budgets=(0,4,12)):
    reports = []
    for budget in budgets:
        rr,vv = train(documents,budget)
        count = sum(len(encode(t,rr)) for t in documents)
        nbytes = sum(len(t.encode('utf8')) for t in documents)
        reports.append(dict(requested_merges=budget,actual_merges=len(rr),
            tokens=count,bytes=nbytes,bytes_per_token=nbytes/count if count else None))
    return reports
print('bundled corpus compression, not external benchmark',compression_report(training))

The previous helper reports compression on its training documents only. Use the following wrapper for the original held-out budget comparison. It fits each budget on training documents, serializes that artifact and evaluates held-out documents without fitting again. Exact duplicate documents are rejected across the split; near-duplicate/document-group auditing remains the caller's responsibility. Repeating an item in training deliberately weights its pairs, so deduplication is a distribution decision, not a semantics-free cleanup.

def heldout_compression(train_docs,heldout_docs,budgets=(0,4,12)):
    train_docs=list(train_docs);heldout_docs=list(heldout_docs)
    if not train_docs or not heldout_docs or set(train_docs)&set(heldout_docs):
        raise ValueError('nonempty document-disjoint splits required')
    reports=[];artifacts={}
    for budget in budgets:
        if type(budget) is not int or budget<0:raise ValueError('nonnegative integer budget')
        rr,vv=train(train_docs,budget)
        encoded=export_artifact(rr,vv)
        restored_rules,restored_vocab=import_artifact(*encoded)
        assert restored_rules==rr and restored_vocab==vv
        artifacts[budget]=encoded
        row={'requested_merges':budget,'actual_merges':len(rr),
             'artifact_sha256':hashlib.sha256(('\0'.join(encoded)).encode()).hexdigest(),
             'merge_preview':[(repr(vv[a]),repr(vv[b]),new) for (a,b),new in rr[:30]]}
        for label,docs in [('train',train_docs),('heldout',heldout_docs)]:
            ids=[encode(t,restored_rules) for t in docs]
            assert all(decode(v,restored_vocab)==t for v,t in zip(ids,docs))
            tokens=sum(map(len,ids));nbytes=sum(len(t.encode('utf8')) for t in docs)
            chars=sum(map(len,docs))
            row[label]={'documents':len(docs),'bytes':nbytes,'characters':chars,'tokens':tokens,
                'bytes_per_token':nbytes/tokens if tokens else None,
                'characters_per_token':chars/tokens if tokens else None}
        reports.append(row)
    return reports,artifacts
 
if __name__=='__main__':
    heldout_report,frozen=heldout_compression(['abababab','café café'],['abac','తెలుగు🙂'])
    assert heldout_report[0]['heldout']['bytes_per_token']==1.
    assert all(r['heldout']['tokens']<=r['heldout']['bytes'] for r in heldout_report)
    try:heldout_compression(['same'],['same'])
    except ValueError:pass
    else:raise AssertionError('split leakage accepted')
    print('bundled train/heldout compression, not a language ranking',heldout_report)

The plot uses actual learned merges on the horizontal axis, not the requested budget when the count threshold stopped training early. Blue is training and red is held-out characters per token; these are Unicode code points, not grapheme clusters. Repeated horizontal positions reveal an exhausted merge budget rather than a hidden plateau claim.

def compression_svg(reports,path):
    from pathlib import Path
    xmax=max(1,max(r['actual_merges'] for r in reports))
    ymax=max(1.,max(r[label]['characters_per_token'] or 0.
                   for r in reports for label in ('train','heldout')))
    parts=['<svg xmlns="http://www.w3.org/2000/svg" width="600" height="320">',
           '<rect width="100%" height="100%" fill="white"/>',
           '<text x="50" y="20">Bundled BPE: characters per token</text>',
           '<path d="M50 40 V250 H550" stroke="black" fill="none"/>']
    for f in (0.,.5,1.):
        parts.append(f'<text x="8" y="{254-200*f}">{ymax*f:.2f}</text>')
        parts.append(f'<text x="{50+500*f}" y="270">{xmax*f:g}</text>')
    for label,color in [('train','blue'),('heldout','red')]:
        points=' '.join(f"{50+500*r['actual_merges']/xmax:.2f},{250-200*r[label]['characters_per_token']/ymax:.2f}"
                        for r in reports if r[label]['characters_per_token'] is not None)
        parts.append(f'<polyline points="{points}" fill="none" stroke="{color}"/>')
    parts.append('<text x="50" y="300" fill="blue">train</text><text x="130" y="300" fill="red">held-out</text><text x="300" y="300">actual learned merges</text></svg>')
    Path(path).write_text(''.join(parts))
 
if __name__=='__main__':
    import os
    if os.environ.get('BPE_FIGURE_PATH'):
        compression_svg(heldout_report,os.environ['BPE_FIGURE_PATH'])

For a permitted local corpus, pass already-split document lists and budgets (500,2000,5000) to this wrapper. Save each returned artifacts[budget] pair as UTF-8 encoder.json and vocab.bpe together with the split/normalization manifest; the preview lists actual learned byte pairs rather than promising English suffixes in a fixed order. Plot each row's requested/actual merges versus train and held-out characters-per-token separately. The bundled fixture tests the procedure, not a 1–10MB run, a 2K-merge optimum or a multilingual quality ranking. import_artifact is a round-trip reader for this trainer's own files, not a comprehensive validator for arbitrary external tokenizers; retain an independently trusted artifact digest before loading someone else's files.

1. BPE in three sentences? Count adjacent symbols on the current training sequences. Merge the selected most frequent pair nonoverlapping with deterministic ties. Save new IDs and rank order and repeat to the stopping condition.
2. Why not longest match? Earlier merges define the trained segmentation; abc with earlierbc givesa,bc, notab,c. The rank test above is a concrete counterexample.
3. Why bytes? All256 byte values permit arbitrary byte coverage; a sampled character alphabet can have unknowns. Strict string encoding and normalization still limit the accepted input contract. Unicode is not infinite.
4. What caused the printed toy trace error? It used newest:2 while claiming the paper's first winner; (l,o) has7 and(e,s) has5. The paper's newest:6 makes a different example.
5. How address artifact tokens? Compare tokenizer/LM distributions, inspect tail frequencies and model behavior, and preserve IDs during any migration. Do not delete every rare token or treat an arbitrary frequency threshold as established best practice.
6. What does Ġthe mean? Space-byte plusthe under GPT-2's visible-byte mapping; not a privileged control token. It differs from barethe.
7. What is the parameter tradeoff? Vd tied, roughly2Vd untied; smaller sequences can help, but compression, output projection and learning quality must all be measured. No twofold vocabulary-to-length law exists.
8. Why keep documents separate? Concatenation teaches artificial boundary pairs. Explicit end-of-document symbols are another specified design, not permission to ignore boundaries.
9. Is lower token perplexity comparable across vocabularies? Not directly: the prediction units changed. Hold tokenizer fixed or report likelihood per fixed byte/character unit with identical text/boundary policy.
10. Can I fit merges on the test set? No: that adapts the representation to held-out data. Freeze the training-fitted artifact with the checkpoint.

Exit test: distinguish bytes, code points, learned pieces and embedding vectors, then reproduce a Unicode round trip and a noncanonical-ID counterexample. Tomorrow inspect whitespace/normalization in SentencePiece; revisit the merge-order trace after a week.

Sources and optional navigation

Primary references: Sennrich et al. §3.2, GPT-2 encoder source, Meta Llama3 tokenizer source, LLaMA paper, Llama3 report, DeepSeek-V3, Mistral NeMo announcement, TokenMonster, vocabulary scaling. Mutable source references are dated and hashed in the evidence, not asserted immutable.

Optional inherited videos: Karpathy tokenizer, BPE overview. No external corpus or model-tokenizer package was downloaded. Course map · Previous DL043 · Next DL045. The former compact-lab links to DL039 and DL046 remain optional shortcuts.