The IDs already exist: recovering minbpe rules and handling special tokens

The previous article’s GPT-2 implementation maps bytes to character aliases, performs string BPE, then looks up IDs in encoder. minbpe’s GPT4Tokenizer merges integer IDs directly, reproducing cl100k_base rather than training a new vocabulary.

Two additional jobs:

• The caller decides whether a registered marker such as <|endoftext|> is recognized, treated literally, or rejected.
• The existing vocabulary supplies complete bytes and rank/ID; integer BPE needs the recovered relation “left ID, right ID → new ID.”

Special markers: text, registered IDs, and stopping

"<|endoftext|>" is first a 13-character Python string. It also spells a registered special token: ID 50256 in GPT-2 and 100257 in cl100k_base. IDs belong to their own vocabularies and cannot be transferred between them.

With tiktoken 0.14.0, the same literal string has three outcomes:

enc = tiktoken.get_encoding("cl100k_base")

enc.encode("<|endoftext|>")                     # ValueError: forbidden by default
enc.encode("<|endoftext|>",
           allowed_special={"<|endoftext|>"})   # [100257]
enc.encode("<|endoftext|>",
           disallowed_special=())              # [27,91,8862,728,428,91,29]

The default error comes from the encoding entry point’s special-marker check, not a failed BPE merge. Allowed markers are recognized as whole segments and mapped directly to registered IDs. Literal handling sends their text through ordinary chunking, bytes, and BPE.

A third layer is how generation interprets the ID. A tokenizer recognizing an ID does not itself stop model generation. Stop-ID lists, message boundaries, and calling protocols belong to the layer above it. The marker’s spelling is not an automatically executed instruction.

cl100k_base registers five markers:

There are 100,256 ordinary entries: 256 single-byte entries and 100,000 merged entries. Special IDs leave gaps. n_vocab = 100277 is the maximum ID plus one, not the number of actual entries.

The published table stores full contents, not parent pairs

Each .tiktoken line contains a Base64-encoded raw byte string and a rank/ID:

IQ==       0      → b'!'
ZQ==       68     → b'e'
aA==       71     → b'h'
bA==       75     → b'l'
bw==       78     → b'o'
aGVsbG8=   15339  → b'hello'

Loading produces mergeable_ranks: dict[bytes, int]. b'hello' → 15339 tells us its full contents and existing ID, but not whether its final merge joined h+ello or he+llo. recover_merges reconstructs that relation.

byte_shuffle changes IDs, not positions

Our part 28 BPE used byte values as base IDs. The official base IDs are a permutation:

byte_shuffle = {
    b: mergeable_ranks[bytes([b])]
    for b in range(256)
}
inverse_byte_shuffle = {idx: b for b, idx in byte_shuffle.items()}

Raw bytes of hello: [104,101,108,108,111]
Remapped base IDs:  [ 71, 68, 75, 75, 78]

ab: [97,98] → [64,65] → BPE → [370]

Despite its name, shuffle only remaps values element by element; their order is unchanged. Nor can arbitrary token IDs be passed to inverse_byte_shuffle: it covers only 256 base IDs, not 15339.

★ Recovering hello: stop before rank 15339

The target b'hello' already has rank r = 15339. Split its raw contents into single bytes:

[h] [e] [l] [l] [o]

The helper bpe looks up the existing rank of every adjacent concatenation. Each round merges one lowest-rank adjacent position, choosing the leftmost on a tie, and permits only rank < r.

Replaying the rules preceding the target leaves its final two components:

left_id  = mergeable_ranks[b"h"]       # 71
right_id = mergeable_ranks[b"ello"]    # 4896
merges[(71, 4896)] = 15339

Allowing the last merge at the target rank would leave only [hello], losing the two components we need. The stopping condition must therefore be min_rank >= max_rank, permitting strictly <, not <=.

This does not count frequencies on new text, choose the commonest pair, or create new IDs. Existing ranks reveal each merged entry’s final connection.

Condensed from karpathy/minbpe, gpt4.py (MIT license):

def earlier_parts(ranks, token, max_rank):
    parts = [bytes([b]) for b in token]
    while len(parts) > 1:
        i = min(range(len(parts) - 1),
                key=lambda i: ranks.get(parts[i] + parts[i + 1], float("inf")))
        rank = ranks.get(parts[i] + parts[i + 1], float("inf"))
        if rank >= max_rank:
            break
        parts[i:i + 2] = [parts[i] + parts[i + 1]]
    return parts

merges = {}
for token, rank in mergeable_ranks.items():
    if len(token) == 1:               # skip 256 base entries
        continue
    parts = earlier_parts(mergeable_ranks, token, max_rank=rank)
    assert len(parts) == 2
    left, right = (mergeable_ranks[p] for p in parts)
    merges[(left, right)] = rank

This condensed helper assumes a finite target rank. The original also supports max_rank=None for an unrestricted run. A result other than two parts should fail instead of silently saving an incomplete rule.

Recovery and ordinary encoding are not identical

Both use fixed rules, but serve different purposes. The recovery cutoff must not leak into ordinary encoding.

Two tables: merges chooses rules, vocab stores full contents

Recovery supplies 100,000 merges entries. Expand the vocabulary ahead of time:

vocab = {idx: bytes([idx]) for idx in range(256)}
for (left, right), new_id in sorted(merges.items(), key=lambda item: item[1]):
    vocab[new_id] = vocab[left] + vocab[right]

Sorting by merged ID — rank in this encoding — ensures children exist before parents. The original relies on the published table’s iteration order; explicit sorting makes the dependency visible.

Crucially, initial bytes([idx]) contains an internal base ID, not necessarily a raw byte value.

vocab[71]    == bytes([71])
vocab[4896]  == bytes([68,75,75,78])
vocab[15339] == bytes([71,68,75,75,78])  # printed directly: b'GDKKN'

b'GDKKN' is not an incorrectly decoded hello. Those internal IDs happen to print as these ASCII characters. Unshuffle each element into [104,101,108,108,111] to obtain raw b'hello'.

Decoding does not recursively traverse a merge tree. Initialization has already expanded and stored every entry.

Ordinary encode completes the final hello merge

[71,68,75,75,78]
     el:301  → [71,301,75,78]
     lo:385  → [71,301,385]
   ello:4896 → [71,4896]
 hello:15339 → [15339]

The first three steps match recovery. Normal encoding has no max_rank=15339 cutoff, so the fourth also executes. Use the recovered merges to choose the lowest-rank current pair and replace all non-overlapping occurrences, until no rule applies or one ID remains.

Mixed text follows the same path:

Input: Hi 你! 😊
Regex chunks: ['Hi', ' 你', '!', ' 😊']
Final IDs: [13347,220,57668,0,27623,232]

The emoji still spans tokens. A Hanzi merging into one token here does not imply every character remains intact.

Initialization always uses hello to illustrate one recovered entry. It belongs to the tokenizer instance, not a new training run for each selected input. Cases include hello, internationalization, repeated ab, mixed text with an emoji, and text with a special marker. Candidate counts only aid the display; encoding decisions still use ranks.

Special policies and decoding: original versus learning implementation

RegexTokenizer supports:

That last behavior differs from tiktoken’s default rejection of other markers. To compare equivalent behavior:

enc.encode(text, allowed_special=chosen, disallowed_special=())

Otherwise the reference may fail before producing IDs. Original RegexTokenizer rejects with an assert, raising AssertionError; the local learning implementation uses explicit ValueError. Keep those behaviors distinct.

Original GPT4Tokenizer.decode has a gap

Original gpt4.py decoding looks up only self.vocab[idx] before unshuffling. Registering a special token does not insert it into this ordinary vocabulary. Thus original GPT4Tokenizer.decode([100257]) raises KeyError. The notes’ tokenizer_lab learning implementation adds a branch:

parts = []
for idx in ids:
    if idx in vocab:
        internal = vocab[idx]
        parts.append(bytes(inverse_byte_shuffle[b] for b in internal))
    elif idx in inverse_special_tokens:
        parts.append(inverse_special_tokens[idx].encode("utf-8"))
    else:
        raise ValueError(f"unknown token ID: {idx}")
return b"".join(parts).decode("utf-8", errors="replace")

Ordinary tokens retrieve internal expanded contents and unshuffle each base ID. Special tokens directly UTF-8-encode their registered spelling, bypassing base-ID unshuffling. Join all byte fragments and decode once.

tokenizer.encode("<|endoftext|>hello", allowed_special="all")
# [100257,15339]
tokenizer.decode([100257,15339])
# '<|endoftext|>hello'

This round trip belongs to the learning implementation with special decoding added, not unmodified gpt4.py.

What the verification covers

The five local tokenizer_lab/verify.py tests passed again:

Inputs include Chinese, combining characters, emoji, zero bytes, tabs, newlines, repeated fragments, and strings generated with a fixed random seed. Boundary checks also cover unknown IDs and UTF-8 fragments spanning tokens. Comparing only final text would miss incorrect token IDs or contents.

These results establish agreement for this environment, vocabulary, and test scope; 123 examples do not prove coverage of every possible string. The implementation reads private attributes including _mergeable_ranks, so retain dependency versions and recheck after changes.

Across these three articles: regex determines boundaries, fixed rank determines merge order, IDs identify vocabulary members, special policies govern marker recognition, and expanded vocab supplies decoding contents. Initialization can do substantial work ahead of time; encoding and decoding then consult the tables appropriate to their own jobs.