Tokenization, Sequence Budgets, and Reproducible Batching

Build small tokenizers, measure their sequence trade-offs, and make causal batches auditable.

Text is not yet a language-model input. A model receives integer IDs, and the tokenizer decides which distinctions become easy, which become expensive, and which disappear behind an unknown token. This chapter implements character, byte, word, and small byte-pair tokenizers before constructing shifted windows and padding masks. The examples use a fixed Unicode-and-code fixture so that every count can be reproduced.

Tokenization is part of the model specification. A checkpoint is not usable without the vocabulary, merge rules, special-token policy, and preprocessing version that produced its IDs.

Tokenization tradeoffs

A tokenizer is a map

\tau: \mathcal{X} \longrightarrow \{0,1,\ldots,V-1\}^{*},

where the star permits variable-length sequences. For a text x, write T(x)=|\tau(x)| for its token count. A fixed model width does not make all tokenizers equally expensive: self-attention over a sequence of length T has score and value-mixing cost proportional to T^2d, while the embedding and output work is roughly proportional to T.

This creates a real trade-off. Character and byte vocabularies are simple and have broad coverage, but they usually make T large. Word vocabularies compress familiar text but require an unknown-token policy and make morphology, spelling, and code punctuation awkward. Byte-pair encoding (BPE) learns frequent pieces, retaining a fallback path while reducing sequence length on the training distribution. The learned merges are themselves data and must be versioned.

The target sequence is not merely a compressed string. Token boundaries influence which conditional distributions the model must learn, how many examples fit in a batch, and whether a rare name or a code operator is represented as a recoverable unit.

Basic tokenizers

The first three implementations make different failure modes visible. The character tokenizer has an unknown character only when text outside its training alphabet appears. The byte tokenizer has a fixed 256-symbol vocabulary and round-trips arbitrary UTF-8 bytes, provided decoding uses an explicit error policy. The word tokenizer is compact on familiar prose but cannot preserve whitespace and maps unseen words to <unk>.

from collections import Counter

import numpy as np


class CharacterTokenizer:
    def __init__(self, training_text: str):
        self.itos = ["<unk>"] + sorted(set(training_text))
        self.stoi = {token: i for i, token in enumerate(self.itos)}

    def encode(self, text: str) -> list[int]:
        return [self.stoi.get(character, 0) for character in text]

    def decode(self, ids) -> str:
        return "".join(self.itos[int(i)] for i in ids if int(i) != 0)


class ByteTokenizer:
    def encode(self, text: str) -> list[int]:
        return list(text.encode("utf-8"))

    def decode(self, ids) -> str:
        return bytes(int(i) for i in ids).decode("utf-8", errors="replace")


class WordTokenizer:
    def __init__(self, training_text: str):
        self.itos = ["<unk>"] + sorted(set(training_text.split()))
        self.stoi = {token: i for i, token in enumerate(self.itos)}

    def encode(self, text: str) -> list[int]:
        return [self.stoi.get(word, 0) for word in text.split()]

    def decode(self, ids) -> str:
        return " ".join(self.itos[int(i)] for i in ids)


sample = "Café robots read code: x += 1.\n"
character = CharacterTokenizer(sample)
byte = ByteTokenizer()
word = WordTokenizer(sample)

encoded = {
    "character": character.encode(sample),
    "byte": byte.encode(sample),
    "word": word.encode(sample),
}
for name, ids in encoded.items():
    print(f"{name:>9}: vocab={len(character.itos) if name == 'character' else 256 if name == 'byte' else len(word.itos):>3}, tokens={len(ids):>2}")

assert character.decode(encoded["character"]) == sample
assert byte.decode(encoded["byte"]) == sample
assert word.encode("unseen-word") == [0]
assert byte.decode([0xC3, 0x28]) == "\ufffd("

character: vocab= 21, tokens=31
     byte: vocab=256, tokens=32
     word: vocab=  8, tokens= 7

The byte tokenizer uses two tokens for é because UTF-8 represents it as two bytes, while the character tokenizer uses one symbol. The word tokenizer is shortest here but its round trip normalizes all whitespace to single spaces and cannot represent an unseen word. Those are not implementation accidents: each tokenizer has made a different promise about coverage and reversibility.

Byte-Pair Encoding (BPE)

BPE starts with small symbols and repeatedly replaces the most frequent adjacent pair. If the current sequence is (s_1,\ldots,s_m) and (a,b) is the selected pair, one merge replaces each adjacent occurrence of (a,b) with a new symbol ab. A deterministic tie rule is necessary; otherwise two trainers can produce different vocabularies from the same corpus.

This miniature version puts an end-of-word marker on each word. Real byte-level implementations use a carefully specified boundary convention and often begin from bytes rather than Unicode characters. The teaching point is the state transition: the corpus statistics select a merge, and the ordered merge list defines future encoding.

def merge_once(sequence, pair):
    merged = []
    i = 0
    while i < len(sequence):
        if i + 1 < len(sequence) and (sequence[i], sequence[i + 1]) == pair:
            merged.append(sequence[i] + sequence[i + 1])
            i += 2
        else:
            merged.append(sequence[i])
            i += 1
    return tuple(merged)


def train_bpe(text: str, num_merges: int = 8):
    sequences = [tuple(list(word) + ["</w>"]) for word in text.casefold().split()]
    merges = []
    for _ in range(num_merges):
        counts = Counter(
            pair
            for sequence in sequences
            for pair in zip(sequence, sequence[1:])
        )
        if not counts:
            break
        # Count is primary; tuple order breaks ties reproducibly.
        pair = max(counts, key=lambda candidate: (counts[candidate], candidate))
        merges.append(pair)
        sequences = [merge_once(sequence, pair) for sequence in sequences]
    return merges


def encode_bpe(text: str, merges):
    tokens = []
    for word in text.casefold().split():
        sequence = tuple(list(word) + ["</w>"])
        for pair in merges:
            sequence = merge_once(sequence, pair)
        tokens.extend(sequence)
    return tokens


merges = train_bpe(sample, num_merges=10)
bpe_tokens = encode_bpe(sample, merges)
print("learned merges:", merges)
print("BPE tokens:", bpe_tokens)
print("character / BPE lengths:", len(encoded["character"]), "/", len(bpe_tokens))
assert train_bpe(sample, 10) == merges
assert len(bpe_tokens) <= len(sample.split()) * (max(map(len, sample.split())) + 1)

learned merges: [('é', '</w>'), ('x', '</w>'), ('t', 's'), ('ts', '</w>'), ('r', 'o'), ('ro', 'b'), ('rob', 'o'), ('robo', 'ts</w>'), ('r', 'e'), ('re', 'a')]
BPE tokens: ['c', 'a', 'f', 'é</w>', 'robots</w>', 'rea', 'd', '</w>', 'c', 'o', 'd', 'e', ':', '</w>', 'x</w>', '+', '=', '</w>', '1', '.', '</w>']
character / BPE lengths: 31 / 21

The merge list is reproducible because both the pair counts and the tie rule are fixed. A merge vocabulary is useful only together with its training alphabet, boundary markers, and ordering; storing the final pieces without the merge history makes exact re-encoding harder to audit. The toy BPE is intentionally small, but it exposes the same state that a production tokenizer must serialize.

A normalized BPE round trip

The toy BPE representation has a deliberate normalization boundary: it lowercases words and treats whitespace as a separator. Decode that representation back to normalized text before using it as a language-model vocabulary. This is a valid round trip for the tokenizer’s declared contract; it is not a promise to recover the original capitalization or spacing.

def decode_bpe(tokens):
    words = []
    current = []
    for token in tokens:
        if token.endswith("</w>"):
            current.append(token[:-4])
            words.append("".join(current))
            current = []
        else:
            current.append(token)
    if current:
        words.append("".join(current))
    return " ".join(words)

normalized_sample = " ".join(sample.casefold().split())
print("normalized BPE decode:", decode_bpe(bpe_tokens))
assert decode_bpe(bpe_tokens) == normalized_sample
assert decode_bpe(encode_bpe("", merges)) == ""
assert decode_bpe(encode_bpe("Café", merges)) == "café"

normalized BPE decode: café robots read code: x += 1.

Causal windows

A language-model example uses an input window and the same window shifted one token to the right as its targets. A batcher must preserve that shift, identify padding separately from content, and expose the causal visibility relation to the model. The following functions keep those responsibilities separate: make_windows creates training pairs, pad_batch creates rectangular arrays, pack_documents inserts an explicit boundary, and causal_attention_mask combines padding with the lower-triangular causal relation.

def make_windows(tokens, context_length, stride):
    tokens = list(tokens)
    if context_length < 1 or stride < 1:
        raise ValueError("context_length and stride must be positive")
    last_start = len(tokens) - context_length
    if last_start <= 0:
        return []
    return [
        (
            np.asarray(tokens[start:start + context_length], dtype=np.int64),
            np.asarray(tokens[start + 1:start + context_length + 1], dtype=np.int64),
        )
        for start in range(0, last_start, stride)
    ]


def pad_batch(sequences, pad_id, max_length=None):
    sequences = [np.asarray(sequence, dtype=np.int64) for sequence in sequences]
    if not sequences:
        return np.empty((0, 0), dtype=np.int64), np.empty((0, 0), dtype=bool)
    natural_length = max(len(sequence) for sequence in sequences)
    length = natural_length if max_length is None else max(0, int(max_length))
    batch = np.full((len(sequences), length), pad_id, dtype=np.int64)
    valid = np.zeros((len(sequences), length), dtype=bool)
    for row, sequence in enumerate(sequences):
        clipped = sequence[:length]
        batch[row, :len(clipped)] = clipped
        valid[row, :len(clipped)] = True
    return batch, valid


def pack_documents(documents, eos_id):
    packed = []
    for document in documents:
        packed.extend(document)
        packed.append(eos_id)
    return np.asarray(packed, dtype=np.int64)


def causal_attention_mask(valid_tokens):
    valid_tokens = np.asarray(valid_tokens, dtype=bool)
    if valid_tokens.ndim != 2:
        raise ValueError("valid_tokens must have shape (batch, time)")
    batch, time = valid_tokens.shape
    lower_triangle = np.tril(np.ones((time, time), dtype=bool))
    return (
        lower_triangle[None, :, :]
        & valid_tokens[:, :, None]
        & valid_tokens[:, None, :]
    )


window_inputs, window_targets = make_windows(range(7), context_length=4, stride=2)[0]
print("first window:", window_inputs.tolist(), "->", window_targets.tolist())
assert np.array_equal(window_inputs, [0, 1, 2, 3])
assert np.array_equal(window_targets, [1, 2, 3, 4])
assert make_windows([], 3, 1) == []

batch, valid = pad_batch([[4, 5, 6], [7]], pad_id=0)
mask = causal_attention_mask(valid)
print("padded batch:\n", batch)
print("valid-token mask:\n", valid.astype(int))
assert batch.tolist() == [[4, 5, 6], [7, 0, 0]]
assert valid.tolist() == [[True, True, True], [True, False, False]]
assert mask.shape == (2, 3, 3)
assert not bool(mask[0, 1, 2])
assert not mask[1, 1].any()
assert pack_documents([[1, 2], [3]], eos_id=9).tolist() == [1, 2, 9, 3, 9]

first window: [0, 1, 2, 3] -> [1, 2, 3, 4]
padded batch:
 [[4 5 6]
 [7 0 0]]
valid-token mask:
 [[1 1 1]
 [1 0 0]]

The shift test checks target leakage directly: the target at position t is the token at input position t+1, never a copy of the input at the same position. Padding is represented by a separate Boolean array, so an ID that happens to equal the padding value cannot be mistaken for a valid token. The combined attention mask also removes padded queries and keys; a causal triangle alone would still let padded positions participate in computation.

Packing inserts an end-of-document token before concatenation. Without that boundary, a target at the end of one document would ask the model to predict the first token of an unrelated document as though the two texts were continuous.

Token counts and sequence length

The corpus below contains repeated prose, Unicode, whitespace, and code-like punctuation. The repeated structure makes a short experiment stable while the special characters keep the representations different. Compare total tokens, average tokens per document, and the quadratic attention-work proxy \sum_i T_i^2. The last quantity is a useful reminder that a tokenizer which is only 20 percent shorter can remove substantially more attention work.

corpus = [
    "Café robots read code: x += 1.",
    "Café robots write tests; naïve bugs become visible.",
    "A short context lets the model see nearby symbols.",
    "def add(x, y): return x + y  # deterministic",
] * 3

corpus_character = CharacterTokenizer("\n".join(corpus))
corpus_word = WordTokenizer("\n".join(corpus))
corpus_merges = train_bpe("\n".join(corpus), num_merges=24)
corpus_sequences = {
    "character": [corpus_character.encode(text) for text in corpus],
    "byte": [byte.encode(text) for text in corpus],
    "word": [corpus_word.encode(text) for text in corpus],
    "bpe": [encode_bpe(text, corpus_merges) for text in corpus],
}

for name, sequences in corpus_sequences.items():
    lengths = np.asarray([len(sequence) for sequence in sequences])
    total_characters = sum(len(text) for text in corpus)
    total_tokens = int(lengths.sum())
    print(
        f"{name:>9}: total={total_tokens:>3}, mean={lengths.mean():5.1f}, "
        f"chars/token={total_characters / total_tokens:4.2f}, "
        f"sum(T^2)={int((lengths ** 2).sum()):>5}"
    )

assert corpus_character.decode(corpus_sequences["character"][0]) == corpus[0]
assert byte.decode(corpus_sequences["byte"][0]) == corpus[0]
assert corpus_word.decode(corpus_sequences["word"][0]) == " ".join(corpus[0].split())
assert decode_bpe(corpus_sequences["bpe"][0]) == " ".join(corpus[0].casefold().split())

character: total=525, mean= 43.8, chars/token=1.00, sum(T^2)=23811
     byte: total=534, mean= 44.5, chars/token=0.98, sum(T^2)=24618
     word: total= 99, mean=  8.2, chars/token=5.30, sum(T^2)=  825
      bpe: total=357, mean= 29.8, chars/token=1.47, sum(T^2)=11667

The character and byte rows preserve the original strings, but they spend more positions on multibyte text and punctuation. The word row has the smallest familiar-prose representation in this fixture because it discards whitespace and treats punctuation-attached words as single entries; that same policy makes code: and code different vocabulary items. BPE sits between the two extremes because its merge budget is spent on pairs that recur in this corpus. The quadratic column is the relevant comparison for attention memory, not only the linear token count.

Padding and vocabulary size

A batch is rectangular even when documents are not. Measure the fraction of valid positions after padding the same corpus under each tokenizer, then vary the BPE merge budget. A larger vocabulary does not guarantee shorter sequences: only merges supported by the data reduce this corpus’s token count, and a vocabulary trained on a different distribution can spend entries on the wrong pairs.

bpe_pieces = sorted({piece for sequence in corpus_sequences["bpe"] for piece in sequence})
bpe_piece_to_id = {piece: index + 1 for index, piece in enumerate(bpe_pieces)}
integer_sequences = {
    name: sequences
    for name, sequences in corpus_sequences.items()
    if name != "bpe"
}
integer_sequences["bpe"] = [
    [bpe_piece_to_id[piece] for piece in sequence]
    for sequence in corpus_sequences["bpe"]
]

for name, sequences in integer_sequences.items():
    padded, valid = pad_batch(sequences, pad_id=0)
    utilization = float(valid.mean())
    print(f"{name:>9}: padded shape={padded.shape}, valid fraction={utilization:.3f}")

print("\nBPE merge sweep")
for merge_count in (0, 4, 8, 16, 24, 40):
    sweep_merges = train_bpe("\n".join(corpus), num_merges=merge_count)
    sweep_lengths = [len(encode_bpe(text, sweep_merges)) for text in corpus]
    print(
        f"merges={merge_count:>2}, learned={len(sweep_merges):>2}, "
        f"mean tokens={np.mean(sweep_lengths):5.1f}, "
        f"chars/token={sum(map(len, corpus)) / sum(sweep_lengths):4.2f}"
    )

assert pad_batch([], pad_id=0)[0].shape == (0, 0)
assert all(len(sequence) > 0 for sequence in integer_sequences["bpe"])

character: padded shape=(12, 51), valid fraction=0.858
     byte: padded shape=(12, 53), valid fraction=0.840
     word: padded shape=(12, 9), valid fraction=0.917
      bpe: padded shape=(12, 38), valid fraction=0.783

BPE merge sweep
merges= 0, learned= 0, mean tokens= 44.5, chars/token=0.98
merges= 4, learned= 4, mean tokens= 40.5, chars/token=1.08
merges= 8, learned= 8, mean tokens= 37.5, chars/token=1.17
merges=16, learned=16, mean tokens= 33.5, chars/token=1.31
merges=24, learned=24, mean tokens= 29.8, chars/token=1.47
merges=40, learned=40, mean tokens= 25.8, chars/token=1.70

Special tokens

Padding, document boundaries, and sequence boundaries need IDs that cannot collide with ordinary content. Reserve them in a vocabulary registry before encoding. The registry below keeps the four roles explicit; pad_batch can then use the registered padding ID without treating an ordinary token as padding.

class SpecialTokenRegistry:
    def __init__(self, base_vocabulary_size):
        names = ("<pad>", "<bos>", "<eos>", "<unk>")
        self.stoi = {
            name: base_vocabulary_size + index
            for index, name in enumerate(names)
        }

    def wrap(self, token_ids):
        return [self.stoi["<bos>"]] + list(token_ids) + [self.stoi["<eos>"]]


special_tokens = SpecialTokenRegistry(base_vocabulary_size=len(corpus_character.itos))
wrapped_empty = special_tokens.wrap([])
wrapped_sample = special_tokens.wrap(corpus_sequences["character"][0][:4])
special_batch, special_valid = pad_batch(
    [wrapped_sample, wrapped_empty], pad_id=special_tokens.stoi["<pad>"]
)
truncated, truncated_valid = pad_batch(
    [[1, 2, 3]], pad_id=special_tokens.stoi["<pad>"], max_length=2
)
print("special-token IDs:", special_tokens.stoi)
print("wrapped empty sequence:", wrapped_empty)
print("special-token batch:\n", special_batch)
assert wrapped_empty == [special_tokens.stoi["<bos>"], special_tokens.stoi["<eos>"]]
assert special_batch[1, 1] == special_tokens.stoi["<eos>"]
assert not special_valid[1, 2]
assert special_tokens.stoi["<pad>"] not in corpus_sequences["character"][0]
assert truncated.tolist() == [[1, 2]]
assert truncated_valid.tolist() == [[True, True]]

long_text = "Café robots " * 400
assert corpus_character.decode(corpus_character.encode("")) == ""
assert byte.decode(byte.encode("")) == ""
assert corpus_word.decode(corpus_word.encode("")) == ""
assert corpus_character.decode(corpus_character.encode(long_text)) == long_text
assert byte.decode(byte.encode(long_text)) == long_text
assert decode_bpe(encode_bpe(long_text, corpus_merges)) == " ".join(long_text.casefold().split())
print("empty and long round trips: passed")

special-token IDs: {'<pad>': 38, '<bos>': 39, '<eos>': 40, '<unk>': 41}
wrapped empty sequence: [39, 40]
special-token batch:
 [[39 14 15 20 36 40]
 [39 40 38 38 38 38]]
empty and long round trips: passed

The registry gives <pad>, <bos>, <eos>, and <unk> distinct IDs above the base vocabulary. An empty document still has a meaningful boundary pair, while the second padded row has an end marker followed by invalid positions. Reserving these IDs before encoding prevents a later vocabulary extension from changing the meaning of a stored padding mask.

max_length=2 demonstrates right truncation explicitly: the third token is removed before padding, and the validity mask still describes the retained positions. Padding utilization is a property of the batching policy as well as the tokenizer. Sorting examples by length or packing compatible documents can reduce wasted positions, but packing must retain document boundaries and loss masks. The merge sweep makes the compression curve visible: early merges usually remove repeated local patterns, while later merges have diminishing effect on this fixed corpus. A validation corpus is needed before selecting a merge count, because compression measured only on training text rewards vocabulary memorization.

Frozen byte-level BPE artifact

The small tokenizers above stay in the chapter because their failure modes are useful. The reusable path now trains a real byte-level BPE on the checked mixed-corpus sample. Its special-token map and serialized identity are part of the artifact, so later chapters do not reconstruct a vocabulary from notebook-local state. This smoke artifact uses a small fixture and a 512-token budget; the standard profile raises the sample and vocabulary budgets without changing the contract.

from pathlib import Path

from proof_lm.data import (
    batch_packed_examples,
    build_mixed_smoke_corpus,
    mixed_smoke_texts,
    pack_causal_examples,
)
from proof_lm.tokenization import (
    DEFAULT_SPECIAL_TOKENS,
    load_tokenizer_artifact,
    train_byte_level_bpe,
)

mixed_dataset, mixed_manifest = build_mixed_smoke_corpus(seed=17, proof_count=12)
checked_texts = mixed_smoke_texts(seed=17, proof_count=12)
real_tokenizer = train_byte_level_bpe(
    checked_texts,
    training_dataset_id=mixed_dataset.dataset_manifest_id,
    vocab_size=512,
    min_frequency=1,
)
artifact_dir = Path("projects/proof-lm/artifacts/tokenizers/mixed-smoke-v1")
tokenizer_path, manifest_path = real_tokenizer.save(artifact_dir)
reloaded_tokenizer = load_tokenizer_artifact(artifact_dir)

real_sequences = reloaded_tokenizer.encode_batch(checked_texts)
lengths = np.asarray([len(sequence) for sequence in real_sequences])
formula_text = "P -> (Q & !R)"
fallback_text = "Café λx. proof ✓ 🧪"
formula_ids = reloaded_tokenizer.encode(formula_text)
fallback_ids = reloaded_tokenizer.encode(fallback_text)
unknown_id = reloaded_tokenizer.token_id("<|unk|>")
pad_id = reloaded_tokenizer.token_id("<|pad|>")
real_batch, real_valid = pad_batch(real_sequences, pad_id=pad_id)
long_ids = reloaded_tokenizer.encode("Café proof " * 300)
truncated_batch, truncated_valid = pad_batch(
    [long_ids], pad_id=pad_id, max_length=512
)

packed_examples = pack_causal_examples(
    real_sequences,
    eos_id=reloaded_tokenizer.token_id("<|eos|>"),
    pad_id=pad_id,
    context_length=32,
    stride=32,
)
packed_batches = batch_packed_examples(packed_examples, batch_size=4)
packed_valid_tokens = sum(
    sum(example.valid_mask) for example in packed_examples
)
packed_loss_tokens = sum(
    sum(example.loss_mask) for example in packed_examples
)
special_ids_match = all(
    reloaded_tokenizer.token_id(token)
    == reloaded_tokenizer.manifest.special_tokens[token]
    for token in DEFAULT_SPECIAL_TOKENS
)

print("tokenizer id:", reloaded_tokenizer.manifest.tokenizer_id)
print("vocab size:", reloaded_tokenizer.manifest.vocab_size)
print("special-token count:", len(DEFAULT_SPECIAL_TOKENS))
print("checked texts:", len(checked_texts))
print("mean tokens:", round(float(lengths.mean()), 1))
print("formula / proof lengths:", len(formula_ids), len(real_sequences[-1]))
print("fallback unknown count:", fallback_ids.count(unknown_id))
print("padding utilization:", round(float(real_valid.mean()), 3))
print("long / truncated lengths:", len(long_ids), truncated_batch.shape[1])
print("packed examples / batches:", len(packed_examples), len(packed_batches))
print("boundary-masked targets:", packed_valid_tokens - packed_loss_tokens)
print(
    "hash prefixes:",
    reloaded_tokenizer.manifest.vocabulary_sha256[:12],
    reloaded_tokenizer.manifest.merges_sha256[:12],
    reloaded_tokenizer.manifest.tokenizer_sha256[:12],
)
print("saved artifact:", tokenizer_path)

assert len(mixed_manifest) == len(checked_texts)
assert reloaded_tokenizer.manifest == real_tokenizer.manifest
assert special_ids_match
assert (
    reloaded_tokenizer.decode(reloaded_tokenizer.encode(fallback_text))
    == fallback_text
)
assert fallback_ids.count(unknown_id) == 0
assert real_batch.shape[0] == len(checked_texts)
assert real_valid.shape == real_batch.shape
assert len(long_ids) > truncated_batch.shape[1] == 512
assert truncated_valid.all()
assert packed_batches
assert all(
    len(example.input_ids) == 32 for example in packed_examples
)
assert 0 < packed_loss_tokens < packed_valid_tokens

tokenizer id: tok-9d776c21447b83db
vocab size: 430
special-token count: 15
checked texts: 40
mean tokens: 45.7
formula / proof lengths: 13 56
fallback unknown count: 0
padding utilization: 0.817
long / truncated lengths: 2100 512
packed examples / batches: 59 15
boundary-masked targets: 39
hash prefixes: 04cb49e027e6 fadf48109968 3681026e9f3c
saved artifact: projects/proof-lm/artifacts/tokenizers/mixed-smoke-v1/tokenizer.json

Summary

• Character, byte, word, and toy BPE tokenizers make different coverage and reversibility promises.
• BPE is a sequence of deterministic pair replacements; the ordered merge list is part of the checkpoint contract.
• The reusable byte-level BPE artifact freezes vocabulary, special-token IDs, serialization, and dataset identity.
• Shifted windows, padding masks, and document-boundary tokens prevent target leakage and cross-document examples.
• Token count, padding utilization, and the quadratic attention-work proxy expose the compute consequences of tokenization.
• Compression must be measured on held-out text, with unknown-token and special-token behavior tested explicitly.

Chapter 03 uses these token IDs to build models whose likelihood and gradients can be checked against direct calculations.

Exercises

Use the exercises to test the chapter’s invariants and connect the derivations to the reusable implementation. Solutions are hidden in the notebook source and are available through the course tooling when needed.

[P2.1] Causal window invariants

Window audit. For tokens 0 through 9, use context length 4 and stride 3. Report every input-target pair, then state the two assertions that rule out same-position targets and future-token visibility.

[P2.2] Tokenization compression and round trips

Compression audit. Explain why a byte tokenizer can use more tokens than a character tokenizer for one Unicode string, and compute the character-to-byte ratio for “éx”. State which round-trip promise the word tokenizer in this chapter does not make.

[P2.3]

Tokenizer artifact identity. A checkpoint must reject a tokenizer whose special-token map is incomplete or has duplicate IDs. Implement validate_special_ids(manifest, required_tokens) so it returns True exactly when every required token is present and all corresponding IDs are unique.

def validate_special_ids(manifest, required_tokens):
    # Check presence and uniqueness without changing the manifest.
    pass