mirror of
https://github.com/harvard-edge/cs249r_book.git
synced 2026-11-10 15:05:34 -06:00
320 lines
38 KiB
Plaintext
320 lines
38 KiB
Plaintext
# Byte-Pair Encoding: Compressing Language into Subword Tokens {#sec-tokenization}
|
|
|
|
::: {.column-margin}
|
|
{width="100%" fig-alt="TinyTorch execution datapath blueprint highlighting Module 10 Tokenization as the active subsystem."}
|
|
|
|
*Framework Blueprint: Module 10 bridges unstructured text and tensor mathematics through Byte-Pair Encoding subword tokenization.*
|
|
:::
|
|
|
|
|
|
Language models operate over discrete symbolic text, yet neural networks compute strictly over continuous floating-point vectors. The fundamental challenge of natural language processing is bridging this representational divide: how do we convert variable-length human text into structured numerical sequences? Character-level tokenization produces long sequences, and attention's cost grows with the square of sequence length; word-level tokenization creates large vocabularies that have no ID for an unseen word.
|
|
|
|
In modern deep learning, subword tokenization turns strings into integer token arrays in a single method call:
|
|
|
|
```python
|
|
from transformers import AutoTokenizer
|
|
|
|
tokenizer = AutoTokenizer.from_pretrained("gpt2")
|
|
text = "Machine learning systems from scratch"
|
|
tokens = tokenizer.encode(text)
|
|
|
|
print("Token IDs:", tokens) # [35890, 4673, 3131, 422, 9081]
|
|
print("Subwords:", [tokenizer.decode([t]) for t in tokens])
|
|
# ['Machine', ' learning', ' systems', ' from', ' scratch']
|
|
```
|
|
|
|
Underneath that simple call, the tokenizer executes a statistical compression algorithm:
|
|
|
|
1. **Ordered merge rule traversal:** The engine breaks text into base characters, then iteratively scans and merges the most frequent adjacent pairs according to a pretrained priority table, compressing common words into single integer IDs.
|
|
2. **Elimination of out-of-vocabulary tokens:** By starting from all 256 byte values and building subwords hierarchically, a byte-level tokenizer can represent any text; a character alphabet covers novel words but not unseen characters.
|
|
3. **Sequence length compression:** Subword chunking reduces sequence lengths by $3\times$ to $4\times$ compared to character-level representations, directly mitigating the quadratic $O(S^2)$ memory and compute costs of downstream attention layers (@sec-attention).
|
|
|
|
This chapter constructs TinyTorch's BPE tokenization engine, establishing the text ingestion bridge that feeds the embedding tables in @sec-embeddings and powers language modeling in @sec-transformers. Before building the merge algorithm, we must inspect why naive character-level and word-level strategies fail in opposite directions.
|
|
|
|
---
|
|
|
|
## The Problem
|
|
|
|
::: {.column-margin}
|
|
**↩ Jump back:** @sec-dataloader
|
|
*Tokenization acts as the front-end CPU ingestion stage that feeds numerical tensor batches.*
|
|
:::
|
|
|
|
|
|
There are two obvious ways to turn text into integers, and both fail, in opposite directions.
|
|
|
|
The first is to number the characters. Every observed character gets an ID, but unseen characters remain a problem. A byte tokenizer can instead reserve an ID for each of the 256 byte values and represent any UTF-8 input as bytes. The cost is length. For the text `"the cat sat"`, character tokenization needs eleven IDs, including the spaces; word tokenization needs three. A longer sequence requires more positions to process. In @sec-attention, attention will introduce a table with one entry for every pair of token positions, making sequence length especially consequential; downstream in @sec-memoization, this sequence length directly dictates the memory footprint of the autoregressive key-value cache.
|
|
|
|
The second is to number the words. Split on spaces, give each distinct word an ID, and a 1,000-word essay is 1,000 tokens. Now the vocabulary is the problem. The listing below builds a word vocabulary from one sentence and then encodes three others. Any word the vocabulary has not seen maps to a reserved ID, conventionally written `<unk>` for "unknown".
|
|
|
|
```python
|
|
train_words = "the cat sat on the mat".split()
|
|
vocab = {word: i + 1 for i, word in enumerate(sorted(set(train_words)))} # id 0 is <unk>
|
|
|
|
def encode_words(text):
|
|
return [vocab.get(word, 0) for word in text.split()]
|
|
|
|
print(encode_words("the cat sat")) # [5, 1, 4]
|
|
print(encode_words("the cats sat")) # [5, 0, 4] one extra letter and the word is gone
|
|
print(encode_words("The cat sat.")) # [0, 1, 0] a capital and a period lose two words
|
|
```
|
|
|
|
One plural and the model reads nothing where "cats" was. A capital letter and a period erase two of three words. Real text is full of plurals, capitals, typos, names, code, and words coined last week, so increasing a word vocabulary cannot guarantee that the next word is present. Size has its own cost. The lookup operation in @sec-embeddings turns each token ID into a row of a lookup table with one entry per vocabulary word and $D$ numbers per row, so, for example, a hypothetical vocabulary of one million words at $D = 4{,}096$ in 32-bit floats is $10^6 \times 4{,}096 \times 4$ bytes, about 16 GB, before the model has read a single word.
|
|
|
|
::: {.column-margin}
|
|
**↪ Jump ahead:** @sec-embeddings
|
|
*How discrete token IDs index into continuous, high-dimensional vector representations via row-gather operations.*
|
|
:::
|
|
|
|
The two extremes trade one cost for the other. Characters give a tiny table and long sequences; words give short sequences and an enormous, leaky table. What we want is in between. Common words should be single tokens, so sequences stay short. Rare words should split into pieces the vocabulary does know, so an unseen word can still retain its known characters. The split itself should be learned from data rather than written by hand, because no one can list the useful pieces of every language.
|
|
|
|
::: {.callout-tip title="Pause & Predict: The Byte-Level Vocab Guarantee"}
|
|
A character-level vocabulary has ~100 tokens but produces long sequences. A word-level vocabulary has >500,000 tokens but suffers from out-of-vocabulary (OOV) unknown words. How does byte-level Byte-Pair Encoding (BPE) guarantee both a compact vocabulary (~50,000 tokens) and that no input string can ever produce an out-of-vocabulary token?
|
|
:::
|
|
|
|
---
|
|
|
|
## The Idea
|
|
|
|
::: {.column-margin}
|
|
{width="100%"}
|
|
*BPE pair frequency decay across merge ranks.*
|
|
:::
|
|
|
|
BPE began as a compression technique; [Sennrich, Haddow, and Birch applied it to translation](https://aclanthology.org/P16-1162/) to represent rare words through subword units. The compression origin is the right way to think about it. A compressor looks for repeated patterns and gives them short codes. BPE looks for the most repeated adjacent pair of symbols and gives it a new symbol.
|
|
|
|
Start with an alphabet. Module 10 uses the characters that occur in the training words, with a marker glued onto each word's last character so that a letter ending a word is a different symbol from the same letter inside one; GPT-2 uses the 256 possible byte values instead, and the production section says why.[^fn-gpt2-byte-encoding] Write the training text as a sequence of those symbols. Then repeat one step. Count how often every adjacent pair occurs, pick the pair with the highest count, invent a new symbol for it, and replace every occurrence of the pair with that symbol. In symbols, with $\text{count}(a, b)$ the number of times symbol $a$ is immediately followed by symbol $b$ anywhere in the corpus,
|
|
|
|
$$(a^*, b^*) = \arg\max_{(a, b)} \text{count}(a, b), \qquad \text{new symbol } c = a^* b^*.$$
|
|
|
|
[^fn-gpt2-byte-encoding]: In standard UTF-8, control characters (bytes 0 to 31, 127 to 159) and whitespace cannot be rendered cleanly in regex parsers. GPT-2 solves this by building an explicit invertible bijection `bytes_to_unicode()` that maps all 256 byte values directly into printable Unicode code points (such as shifting byte 32 space to `Ġ` U+0120), ensuring that BPE can run standard Python string regexes without corrupting control characters or byte sequences.
|
|
|
|
A new vocabulary entry can replace many occurrences of its pair; each nonoverlapping replacement shrinks a word by one symbol. The vocabulary ends up holding "es", "est", and so on up to whole common words, each earned by frequency, and the merges are recorded in the order they were made. That ordered list, together with the alphabet and ID mappings, specifies how text is represented. Training runs once, over a large corpus, and produces the list; each new vocabulary entry adds to the initial alphabet and reserved symbols. The requested `vocab_size` is a target for that total, not a count of merges; training may stop sooner when no pairs remain. It also retains the complete base alphabet when that alphabet alone exceeds the target. The public `vocab_size` reports the actual number of entries.
|
|
|
|
Encoding new text replays the list. Split the text into its base symbols and apply the merges in the order they were learned, each rule rewriting every place it matches, so that a pair learned earlier is always merged before one learned later. Because the merge list is fixed and the order is fixed, the same string always encodes to the same IDs, and a word the tokenizer never saw still encodes, because at worst it stays as single known-character symbols. That is most of the guarantee that word vocabularies could not give. The remainder depends on the alphabet: with characters, a character the corpus never contained still has nowhere to go and becomes `<UNK>`; with bytes there is nothing left to be unknown.
|
|
|
|
Decoding is trivial by comparison. Each ID names a string, so concatenate the strings and normalize whitespace. Word-final tokens already contain a trailing space. The pipeline in @fig-tokenization-spectrum separates the state-changing training loop from encoding with fixed rules. The alphabet decides which characters survive; the merge order decides how they group.
|
|
|
|
{#fig-tokenization-spectrum width="100%" fig-alt="Two rows show training from word counts through vocabulary construction to pair merges, and encoding low from individual symbols through a learned merge to integer IDs."}
|
|
|
|
---
|
|
|
|
## The Code
|
|
|
|
::: {.column-margin}
|
|
{width="100%" fig-alt="Source code mapping card for Module 10 Tokenization showing file path, exported package, and tested primitives."}
|
|
|
|
*Source Code Mapping: Module 10 extracts Byte-Pair Encoding (BPE) vocabulary construction, token encoding, and decoding directly from the working repository.*
|
|
:::
|
|
|
|
The tokenizer is a base class fixing the two-method interface, a character tokenizer that is The Problem's first extreme in code, and the BPE tokenizer, which is where the chapter lives. The BPE class holds a vocabulary in both directions (token to ID and ID to token) and the list of merges in the order they were learned. We call a merge's position in that list its **rank**; rank 0 is the first merge made.
|
|
|
|
### The contract, and the character baseline
|
|
|
|
Production language processing frameworks like Hugging Face `tokenizers` and OpenAI `tiktoken` enforce a strict bidirectional contract between unstructured natural language strings and dense integer sequences. Before introducing statistical subword algorithms, character-level tokenizers illustrate this foundational contract in its simplest, lossless form. The language-model input pipeline begins with these integers. In @sec-embeddings, each ID selects a row of a lookup table, and the model's final layer produces one score per ID, so a tokenizer's job is a fixed two-way mapping between strings and IDs that must not change once the model starts training. The base class says only that much: `encode` and `decode`, each of which a subclass must supply.
|
|
|
|
{{< include _listings/10_tokenization/Tokenizer.qmd >}}
|
|
|
|
The class attributes name the unknown token and the word boundary. `<UNK>` occupies ID 0. `TOK_EOW` is the string `" "`, a single space, appended to the last character of each word. Since `str.split()` removes whitespace before creating words, the boundary cannot collide with their contents. The notation `</w>` makes that invisible suffix visible on the page; the implementation does not replace literal `</w>` text.[^fn-boundary-markers] The character tokenizer is the simplest thing that satisfies the contract, and it makes the trade in The Problem concrete: one ID per character, `<UNK>` at ID 0, and a `build_vocab` that sorts the characters it saw so that two runs on the same corpus agree.
|
|
|
|
[^fn-boundary-markers]: Different subword tokenizers use distinct conventions to preserve whitespace boundaries across merges: Sennrich et al. (2016) used trailing `</w>` (or `@@` continuation markers), Google's SentencePiece uses the Unicode meta-symbol `▁` (U+2581 Lower One Eighth Block), and OpenAI's GPT-2/tiktoken maps raw UTF-8 whitespace bytes into printable Unicode characters such as `Ġ` (U+0120).
|
|
|
|
|
|
{{< include _listings/10_tokenization/CharTokenizer.qmd >}}
|
|
|
|
`encode` is a dictionary lookup per character with `<UNK>` as the default, and `decode` is the reverse lookup joined into a string. A known character survives the round trip, while an unknown character becomes the literal `<UNK>`. No merging occurs, so encoding preserves the character count rather than shortening the sequence. The BPE tokenizer starts from the same alphabet and earns its shorter sequences by merging.
|
|
|
|
### Words and the end-of-word marker
|
|
|
|
Subword tokenizers in models like GPT-2 and SentencePiece must prevent merge operations from bleeding across word boundaries while preserving the ability to reconstruct whitespace during decoding. Boundary markers solve this ambiguity by tagging whether a token terminates a word or sits within an ongoing subword stem. Training has exactly one step, repeated, and before the first step the corpus has to be written as symbols. Module 10 works on words. Its `train` takes a list of text strings, splits each with `str.split()`, counts how often each word occurs, and turns each distinct word into a list of characters once; every pair count from then on is weighted by the word's frequency rather than recounted per occurrence. Two consequences follow. No merge can ever cross a space, because no pair does. And the tokenizer needs a way to tell the `w` that ends `low` from the `w` in the middle of `lower`, because when `decode` glues tokens back together it has to know where to put the spaces. That is the marker's job.
|
|
|
|
{{< include _listings/10_tokenization/BPE_init.qmd >}}
|
|
|
|
{{< include _listings/10_tokenization/BPE_vocab_size.qmd >}}
|
|
|
|
Initialization stores the requested target and empty learned state. The property above counts actual entries, so it starts at zero and changes when training replaces or extends `self.vocab`. Callers need not infer that count from the target.
|
|
|
|
{{< include _listings/10_tokenization/BPE_word_tokens.qmd >}}
|
|
|
|
`_get_word_tokens("low")` returns `['l', 'o', 'w ']`, written `l o w</w>` below. The last character carries the marker as part of the symbol, so `w</w>` and `w` are two different entries of the alphabet from the start, and every merge that reaches the end of a word produces a symbol that says so. Training adds both forms of every observed character, even if a form never occurs in the corpus: after seeing only `ab`, it can still represent `ba`, `a`, and `b`. The boundary nevertheless constrains larger tokens, as the worked trace shows: `low</w>` is a whole-word token that `lowest` can never reuse, because inside `lowest` the `w` has no marker.
|
|
|
|
### Counting and merging pairs
|
|
|
|
At the algorithmic core of Byte-Pair Encoding is the iterative replacement of high-frequency adjacent symbol pairs with newly minted vocabulary IDs. Naive string replacement corrupts token boundaries that have already been formed, demanding an explicit symbol-list representation during both frequency counting and merging passes. Both halves of the step have a tempting shortcut that breaks. For counting, we could ask each candidate pair how often it occurs with a search over the corpus, but that is one full pass per candidate, even though one walk over the symbols can count all candidates. For merging, we could join each word back into a string and call `str.replace`. That is wrong, not slow. After the first merge the symbols are no longer single characters, and a string search cannot see where one symbol ends. Once `es` has been merged, `widest` is the five symbols `w i d es t</w>`; there is no `(s, t</w>)` pair in it, but the letters still read `widest`, and a `replace` on the joined string would happily glue the `s` inside `es` to the `t`. We count in a single pass over the word table with a `Counter`, weighting each pair by its word's frequency, and we merge by walking the list of symbols, where the boundaries are explicit.
|
|
|
|
{{< include _listings/10_tokenization/count_pairs.qmd >}}
|
|
|
|
{{< include _listings/10_tokenization/merge_pair.qmd >}}
|
|
|
|
Notice that `_merge_pair` walks left to right and skips two positions after a match. On the symbols `a a a` with the pair `(a, a)`, that yields `aa a`, not `a aa` and not an overlapping double match. The left-to-right choice fixes how overlapping matches are resolved, but the same rule has to apply during training and encoding, or the two will disagree about how a word splits, and `_apply_merges` below uses the identical loop. The helper's name says "byte pairs" because BPE's name does; the symbols it counts here are characters.
|
|
|
|
{#fig-bpe-merge-collapse width="100%" fig-alt="Diagram showing frequency counting of symbol pairs in dictionary words, selection of highest-frequency pair, and token collapse into subword units."}
|
|
|
|
### Training
|
|
|
|
In large language model pipelines such as LLaMA and GPT-6, tokenizer training is an offline preprocessing phase that freezes the discrete vocabulary before model architecture weights are allocated. This optimization loop balances sequence length compression against the memory footprint of downstream embedding and unembedding matrices. A language-model workflow normally trains its tokenizer before allocating the model. The requested `vocab_size` is stored as `target_vocab_size`; it is a training limit, not a promise about the resulting table. The read-only `vocab_size` property returns `len(self.vocab)`, the actual count that must size the model afterward. The lookup table in @sec-embeddings has one row of $D$ numbers per ID, and the output layer has one score per ID, so every entry we add here is a set of weights the model has to learn; at $D = 4{,}096$ in 32-bit floats that is 16 KB of table per entry, before the output layer. Some base entries are deliberately retained for words absent from the training corpus; larger merged entries earn their storage by shortening sequences.
|
|
|
|
{{< include _listings/10_tokenization/BPE_train.qmd >}}
|
|
|
|
Before the loop, `train` builds a local word-frequency table and local lists of symbols. It replaces the tokenizer's old vocabulary and clears its old merges, so calling it again retrains rather than extending the previous state. Each pass counts pairs, picks the winner, and calls `_merge_pair`, which rewrites those local symbol lists in place. The merged string receives the next ID if it is new, and the pair is appended to `self.merges`. Finally, `_build_mappings` creates both lookup dictionaries. The caller's corpus strings remain unchanged; the tokenizer retains the vocabulary and rules, not the temporary word table.
|
|
|
|
Three things to notice. The loop runs until the vocabulary is full or no pair is left; it does not stop when the best pair occurs only once, so on a small corpus the last merges each glue together two symbols that meet in a single word and nowhere else, one vocabulary entry bought to shorten a single occurrence, with little opportunity for reuse. Hugging Face's [BPE trainer](https://huggingface.co/docs/tokenizers/api/trainers) exposes a `min_frequency` setting; adding one here would stop training once the best pair becomes rare. When two pairs tie, `most_common` returns the one the `Counter` met first, which depends on corpus order; ties are common in small corpora and harmless, but they are why two BPE trainers given the same data can produce slightly different vocabularies. Both counting and rewriting scan the word table on every merge. With $N$ initial symbols across distinct words and $M$ merges, these scans give an $O(NM)$ upper bound; the lists shrink as training proceeds.
|
|
|
|
### Encoding and decoding
|
|
|
|
Every inference request and training iteration in production LLM runtimes (such as vLLM or TensorRT-LLM) relies on the encoder to map raw text into input tensors and the decoder to reconstruct text from generated token logits. Ensuring that new inputs are segmented identically to training data requires the encoder to strictly replay learned merge ranks rather than making greedy subword choices. Text enters through `encode`; a list of predicted IDs can later return through `decode`. Decoding a complete list matters here: the final whitespace normalization means separately decoded tokens cannot simply be concatenated to reproduce whole-sequence decoding. These two methods are the ones that run on every request for the life of the model, and the encoder has one hard requirement. New text must split the way the training text split, because the model only knows the tokens it saw during training.
|
|
|
|
The tempting encoder is greedy: at each position, take the longest string that is in the vocabulary. That is a different segmentation rule and need not reproduce what the trainer saw. The merges were learned on words that already had the earlier merges applied; `st</w>` was learned from words containing `s` and `t</w>` as separate symbols after three earlier merges had run. A greedy encoder can grab a long vocabulary entry that the trainer would never have assembled at that position, and hand the model a token sequence it never saw in training. Replaying the merges in the order they were learned recreates the trainer's conditions exactly, so training text encodes exactly as it did during training, and the result is deterministic.
|
|
|
|
{{< include _listings/10_tokenization/BPE_apply_merges.qmd >}}
|
|
|
|
::: {.column-margin}
|
|
**Core Invariant: Merge Rank Determinism**\
|
|
$$\text{Rank}(\text{pair}) = \text{Order of discovery}$$\
|
|
*Encoder must apply merges strictly in ascending rank order to guarantee deterministic segmentation matching training.*
|
|
:::
|
|
|
|
{{< include _listings/10_tokenization/BPE_encode.qmd >}}
|
|
|
|
`_apply_merges` takes the rules in rank order and, for each one, walks the word with the same skip-two loop as `_merge_pair`. `encode` calls `str.split()`, then `_get_word_tokens` and `_apply_merges` for each word, then maps the resulting strings to IDs. Each helper constructs lists for this call; encoding does not alter the learned vocabulary or merge list. Every returned ID lies between zero and `vocab_size - 1` once the tokenizer has been trained.
|
|
|
|
{#fig-bpe-merge-progression width="100%" fig-alt="Progression diagram showing base character tokens merging to 'lo' at Rank 1, then merging to 'low' at Rank 2."}
|
|
|
|
|
|
Every rule walks the current word whether or not it applies. Four learned rules therefore mean four scans per word, and adding rules increases that work even when a particular word cannot use them. An unseen character falls back to `<UNK>`. A known character in a new position does not: both its internal and word-final forms were reserved during training. The returned Python list has one entry per final token; the dataset and batching machinery of @sec-dataloader can later collect compatible sequences for a model.
|
|
|
|
{{< include _listings/10_tokenization/BPE_decode.qmd >}}
|
|
|
|
`decode` looks each ID up and joins the token strings. It then uses `split()` and `join()` to normalize whitespace and remove the final boundary space. An invalid ID becomes literal `<UNK>`. Whitespace changes even when every character is known: `"low lower\n"` and `"low lower"` encode identically because `str.split()` discards their separators. The round-trip contract is therefore normalized words over the observed character alphabet. Literal marker text such as `</w>` survives when its characters are known; only actual spaces serve as boundaries. A byte alphabet addresses unseen characters, while preserving original whitespace requires changing the preprocessing and decoding rules.
|
|
|
|
---
|
|
|
|
## A Worked Trace
|
|
|
|
We train on the five-word corpus `low`, `low`, `lower`, `newest`, `widest`. It contains ten distinct characters. Training reserves two forms per character, internal and word-final, plus `<UNK>`: twenty-one entries, IDs 0 through 20. Sorting places `d` at ID 1, `d</w>` at ID 2, `e` at ID 3, and so on through `w</w>` at ID 20. A target of 25 leaves room for four merges.
|
|
|
|
The local word table starts as follows; `low` has frequency two, and every other row has frequency one.
|
|
|
|
```text
|
|
low: l o w</w>
|
|
lower: l o w e r</w>
|
|
newest: n e w e s t</w>
|
|
widest: w i d e s t</w>
|
|
```
|
|
|
|
| Rank | Most frequent pair | Count | New ID | Words changed |
|
|
| :--- | :--- | :--- | :--- | :--- |
|
|
| 0 | `(l, o)` | 3 | 21 | `low`, `lower` |
|
|
| 1 | `(lo, w</w>)` | 2 | 22 | `low` |
|
|
| 2 | `(w, e)` | 2 | 23 | `lower`, `newest` |
|
|
| 3 | `(s, t</w>)` | 2 | 24 | `newest`, `widest` |
|
|
|
|
: Four BPE merges after the twenty-one-entry base vocabulary. Counts include word frequency; tied pairs are selected in the order first encountered. {#tbl-bpe-merge-trace tbl-colwidths="[10,30,10,12,38]"}
|
|
|
|
After rank 0, both `low` and `lower` start with the single symbol `lo`. Rank 1 completes `low`, but cannot merge `lo w` inside `lower`, where `w` has no boundary suffix. Rank 2 creates `we` in two words, and rank 3 creates `st</w>` in two words. The resulting table is:
|
|
|
|
```text
|
|
low: low</w>
|
|
lower: lo we r</w>
|
|
newest: n e we st</w>
|
|
widest: w i d e st</w>
|
|
```
|
|
|
|
After rank 3 the vocabulary is full and the loop stops. Had we asked for more, it would have kept going; every remaining pair occurs once, and the module merges those too.
|
|
|
|
Now encode the unseen word `lowest`. Its symbols are `l o w e s t</w>`. `_apply_merges` replays the four rules in rank order, and each row below shows the word after that rule has walked it.
|
|
|
|
1. Rule 0, `(l, o)`: `lo w e s t</w>`.
|
|
2. Rule 1, `(lo, w</w>)`: no match, because the `w` in `lowest` carries no marker; `lo w e s t</w>`.
|
|
3. Rule 2, `(w, e)`: `lo we s t</w>`.
|
|
4. Rule 3, `(s, t</w>)`: `lo we st</w>`.
|
|
|
|
Six characters became three IDs, `[21, 23, 24]`, and neither `lowest` nor `est` as a standalone word was in the training corpus. Notice what the marker did at rule 1. The whole-word token `low</w>` exists in the vocabulary, but `lowest` cannot use it, so the tokenizer splits the word as `lo we st</w>` rather than `low est`; removing the marker would change the candidate pairs, so a byte-level trainer would need its own trace before we could predict its split. The listing below runs the trace and then encodes a string with a non-ASCII letter to distinguish unseen characters from unseen word positions.
|
|
|
|
```python
|
|
from tinytorch.core.tokenization import BPETokenizer
|
|
|
|
corpus = ["low", "low", "lower", "newest", "widest"]
|
|
tok = BPETokenizer(vocab_size=25) # 21 base symbols + 4 merges
|
|
tok.train(corpus)
|
|
|
|
for rank, pair in enumerate(tok.merges):
|
|
print(rank, pair, "->", pair[0] + pair[1], tok.token_to_id[pair[0] + pair[1]])
|
|
|
|
ids = tok.encode("lowest")
|
|
print(ids, [tok.id_to_token[i] for i in ids]) # [21, 23, 24] ['lo', 'we', 'st ']
|
|
assert tok.decode(ids) == "lowest"
|
|
|
|
ids = tok.encode("naïve widest")
|
|
print(ids, [tok.id_to_token[i] for i in ids])
|
|
# [9, 0, 0, 0, 4, 19, 5, 1, 3, 24]
|
|
# ['n', '<UNK>', '<UNK>', '<UNK>', 'e ', 'w', 'i', 'd', 'e', 'st ']
|
|
print(tok.decode(ids)) # n<UNK><UNK><UNK>e widest
|
|
```
|
|
|
|
In lines 3 to 5, `BPETokenizer(vocab_size=25)` trains on the five-word corpus, establishing 21 base symbols and 4 learned merges. The loop in lines 7 to 8 prints the ranked merge rules corresponding to @tbl-bpe-merge-trace. In lines 10 to 12, encoding the unseen word `'lowest'` applies the merge chain to yield token IDs `[21, 23, 24]` (`['lo', 'we', 'st ']`), which decode back losslessly to `'lowest'`.
|
|
|
|
::: {#chk-tokenization-byte-fallback .callout-checkpoint title="Checkpoint: Why TinyTorch's tokenizer still emits UNK"}
|
|
The trace above lost three characters of `naïve` to `<UNK>`, and no further training on this corpus recovers them. TinyTorch's `BPETokenizer` seeds its base vocabulary from the characters it observes, so a character that never appears has no representation at all, and once an input collapses into `<UNK>` its information is gone. Modern LLM tokenizers, GPT-2 and LLaMA among them, avoid that case by seeding the base vocabulary with all 256 byte values ($0\text{x}00$ through $0\text{xFF}$). Any UTF-8 string is then a sequence of known bytes even when no learned subword matches, so those tokenizers have no out-of-vocabulary case to handle. TinyTorch stops at the observed-character alphabet because the merge loop is the mechanism this module teaches, and byte seeding changes only which symbols that loop starts from.
|
|
:::
|
|
|
|
The training target is not the output size. With `BPETokenizer(vocab_size=2)` and corpus `["ab"]`, the five base entries already exceed the target; no merge runs, `vocab_size` is 5, and `encode("ba")` returns `[3, 2]`. Conversely, a target of 100 on the five-word corpus stops at 34 entries after thirteen merges exhaust the available pairs. In both cases, allocate the embedding table in @sec-embeddings from the actual `vocab_size`.
|
|
|
|
::: {.column-margin}
|
|
{width="100%" fig-alt="Diagram contrasting TinyTorch character BPE emitting UNK tokens for unseen characters with byte-level BPE decomposing unseen characters into base 256 byte tokens."}
|
|
|
|
*Byte-level fallback: Seeding all 256 byte values ($0\text{x}00$ through $0\text{xFF}$) ensures arbitrary UTF-8 characters decompose into known byte tokens rather than collapsing into UNK.*
|
|
:::
|
|
|
|
---
|
|
|
|
## From TinyTorch to Production
|
|
|
|
::: {.column-margin}
|
|
{width="100%" fig-alt="Diagram illustrating regex pre-tokenization partitioning text into isolated chunks to restrict BPE merges within word and punctuation boundaries."}
|
|
|
|
*Regex pre-tokenization: Isolating words, punctuation, and whitespace into separate chunks prevents merges across boundaries, preserving punctuation reuse and indentation.*
|
|
:::
|
|
|
|
The reference mechanism makes two production questions concrete. How can a tokenizer preserve text outside its training alphabet? How can it avoid scanning thousands of irrelevant rules for every word? Different tokenizers answer these questions differently, so it is useful to compare specific implementations rather than assume every deployed model uses one scheme.
|
|
|
|
The [released GPT-2 encoder](https://github.com/openai/gpt-2/blob/master/src/encoder.py) begins with UTF-8 bytes, remapped reversibly onto printable characters for its internal string operations. Its base alphabet covers all 256 byte values. It uses a regular expression (`'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+`) to partition text into lexical categories before BPE merges run. This boundary firewall ensures that contractions (such as `'ve`), numbers, and punctuation are never glued across words, preventing the tokenizer from polluting its merge table with combinations like `dog,` or `model?`. Within each chunk, it selects the lowest-ranked available pair and repeats; a cache stores earlier chunk results. Its decoder reconstructs the bytes before interpreting them as UTF-8. These choices preserve the distinction between `"low lower\n"` and `"low lower"`, which TinyTorch intentionally discards. They also explain why a single token's bytes need not form a complete Unicode character: decoding an entire sequence is different from decoding each ID separately.
|
|
|
|
Hugging Face's [BPE model interface](https://huggingface.co/docs/tokenizers/api/models) exposes a vocabulary, ranked merges, and cache capacity, along with choices such as unknown-token handling and a word-ending suffix. Its [trainer](https://huggingface.co/docs/tokenizers/api/trainers) exposes the requested vocabulary size, minimum pair frequency, and initial alphabet. Those settings are part of the tokenizer's behavior, not interchangeable performance switches. A BPE model configured over observed characters does not acquire complete byte coverage merely because the library also supports byte-based preprocessing.
|
|
|
|
| Mechanism | TinyTorch | A production alternative |
|
|
| :--- | :--- | :--- |
|
|
| Base alphabet | Both forms of each observed character, plus `<UNK>` | GPT-2 uses all byte values |
|
|
| Boundaries | Split on whitespace; append a space to each word | GPT-2 retains separators during pattern-based splitting |
|
|
| Encoding work | Scan each word once per learned rule | GPT-2 chooses among available pair ranks and caches chunks |
|
|
| Training limits | Target size, complete base alphabet, exhausted pairs | Hugging Face additionally exposes minimum frequency |
|
|
| Model interface | IDs range from 0 to actual `vocab_size - 1` | Vocabulary and preprocessing must match the model |
|
|
|
|
: Production alternatives address coverage and repeated work while retaining an explicit vocabulary and merge rules. {#tbl-bpe-production-comparison tbl-colwidths="[22,39,39]"}
|
|
|
|
The comparison suggests where to reduce repeated work. Our encoder does repeated work on repeated words; caching could remove it while leaving the IDs unchanged. A trainer can track which words contain a pair and update affected counts rather than scan every word again. Such changes need tests against the simple reference, because an altered tie-break or preprocessing rule can change the learned vocabulary even when the new loop is faster.
|
|
|
|
::: {#psp-tokenization-rust-huggingface .callout-perspective title="Production Bridge: Fast multi-threaded Rust tokenizers"}
|
|
In production systems, tokenizing gigabytes of training data in Python with string loops is a major bottleneck. Modern libraries such as HuggingFace `tokenizers` are implemented in Rust: they memory-map the input text files, use lock-free trie structures or hash tables for fast merge rank lookups, and tokenize across all available CPU cores in parallel via Rayon. During autoregressive inference, the tokenizer also handles incremental streaming decoding without reparsing the entire historical token sequence.
|
|
:::
|
|
|
|
Reserved tokens are the other difference worth naming. TinyTorch reserves one, `<UNK>` at ID 0. Production vocabularies usually reserve a few more, for jobs the merge rules cannot express: a padding token that fills shorter sequences so a batch forms a rectangle, beginning- and end-of-sequence tokens that mark document boundaries, and in chat models, tokens that separate turns. Each is a row of the embedding table and a column of the output layer like any other ID, so it costs parameters and must be learned. Each also needs a rule outside the tokenizer. The loss must skip padding positions, and a generation loop must know which ID means stop. [Synthesis II](synthesis_02.qmd#sec-milestone-2) shows the cost of leaving one out: concatenating sentences with no end-of-sequence token teaches the model to run from one sentence straight into the next.
|
|
|
|
The invariant that reaches the model is more important than either optimization. ID 22 denotes `low</w>` in our trace; another tokenizer can assign that same number to unrelated text. Keeping all IDs in range prevents an indexing error, but it does not detect a mismatched vocabulary. The alphabet, preprocessing, reserved tokens, ID mappings, and ordered merges must travel together with the model. Likewise, changing the vocabulary requires reconsidering the model's input and output dimensions. A model's context limit counts tokens rather than words, so the same amount of text can occupy different fractions of that limit under different segmentations.
|
|
|
|
---
|
|
|
|
## Summary
|
|
|
|
Module 10 turns strings into stable integer sequences without tensors or gradients. `train` splits the corpus into words, counts frequencies, reserves internal and word-final forms of every observed character, and repeatedly merges the most frequent adjacent pair. It mutates the tokenizer's vocabulary and ordered merge list while leaving the caller's text unchanged. The actual `vocab_size` counts the resulting entries, which can be above or below the requested target.
|
|
|
|
`encode` uses that fixed state: split, mark word endings, replay merges, then look up IDs. `decode` joins their strings and normalizes whitespace. Known characters survive in new words and new word positions; unseen characters become `<UNK>`. The alphabet determines coverage, while the learned rules determine segmentation. A byte alphabet and whitespace-preserving preprocessing address separate limitations of this reference. @sec-embeddings accepts the resulting IDs and builds the missing numerical operation: selecting a learned vector for each ID, then representing where that token occurs in the sequence.
|
|
|
|
---
|
|
|
|
## Further Reading
|
|
|
|
- **Sennrich, Haddow, and Birch** (2016). "[Neural machine translation of rare words with subword units](https://arxiv.org/abs/1508.07909)." *ACL*. Byte-pair encoding adapted to text, the algorithm this chapter implements.
|
|
- **Radford et al.** (2019). "[Language models are unsupervised multitask learners](https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf)." *OpenAI*. GPT-2, including the byte-level base alphabet in the production comparison above.
|
|
- **Kudo and Richardson** (2018). "[SentencePiece: a simple and language independent subword tokenizer and detokenizer for neural text processing](https://arxiv.org/abs/1808.06226)." *EMNLP*. Tokenizing raw text, whitespace included, without a language-specific splitting step.
|