4.1B Tokenizers and Byte-Pair Encoding

---

Tokenizer 看起来像 preprocessing，实际是 LLM 的离散接口。它决定模型看到的 token 序列、上下文长度、词表大小、多语言压缩率、特殊 token 协议，以及最终 loss 如何在不同语言和格式之间分配。

形式化地说，tokenizer 是一个不可微函数：

\[ \tau:\text{string}\rightarrow\{0,\ldots,|\mathcal{V}|-1\}^{T}. \]

Transformer 只会建模 \(\tau(x)\)，不会直接看到原始字符串。于是 tokenizer 不是“小工具”，而是把人类文本世界压缩成有限离散 vocabulary 的建模假设。

Why Not Word-Level Tokens

word-level tokenization 会把

I love unbelievable machines.

切成：

I | love | unbelievable | machines

这很自然，但开放文本没有固定词表。人名、URL、代码变量、emoji、拼写错误、数学符号、多语言混合都会产生 out-of-vocabulary。用 <unk> 会丢信息；把 vocabulary 做得极大又会浪费 embedding 和 LM head 参数。

character 或 byte tokenization 没有 OOV，但序列太长。例如 unbelievable 可能变成十几个字符 token，而 attention 的成本近似是 \(O(T^2d)\)。

NoteDefinition: Tokenizer Trade-off

A tokenizer trades vocabulary size for sequence length. Larger vocabularies shorten common strings but increase embedding/output parameters; smaller vocabularies improve coverage but lengthen sequences.

BPE 的思想是在这两端之间折中：从小单位开始，反复合并高频相邻 pair，让常见片段变短，罕见字符串仍能回退到底层单位。

Classical BPE Training

Byte-Pair Encoding 的训练过程：

1. 把 corpus 切成初始符号序列；
2. 统计相邻 symbol pair 的频率；
3. 选择最高频 pair \((a,b)\)；
4. 把所有相邻 \(a,b\) 合并成新 symbol \(ab\)；
5. 重复直到达到目标 vocabulary size 或 merge 数。

玩具 corpus：

low
lower
newest
widest

先按字符加词尾边界：

l o w </w>
l o w e r </w>
n e w e s t </w>
w i d e s t </w>

如果最高频 pair 是 e s，合并成 es：

n e w es t </w>
w i d es t </w>

下一轮可能把 es t 合并成 est。不断重复后，常见词根、后缀、空格前缀会成为 token。

NoteDefinition: BPE Merge Rank

The merge rank is the order in which a symbol pair is added to the BPE merge table. During encoding, lower-rank merges have higher priority.

训练结束后，tokenizer 保存的是 merge table，而不是 corpus 统计：

("e", "s")   -> rank 0
("es", "t") -> rank 1
("l", "o")  -> rank 2
...

encoding 时根据 rank 贪心合并当前字符串里的 pair，直到没有可合并 pair。

BPE as Greedy Compression

BPE 最早可以理解成一种 greedy compression：如果 pair \((a,b)\) 在当前 corpus 表示中出现 \(c(a,b)\) 次，那么把它合并成新 symbol \(ab\) 会让 token 总长度近似减少 \(c(a,b)\)。于是每一步选择最高频 pair，相当于每次做一个局部最强的压缩动作。

如果 corpus 被先统计成 type frequency：

low</w>      count 5
lower</w>    count 2
newest</w>   count 6
widest</w>   count 3

那么 pair frequency 不是简单扫每个 word type 一次，而是加权统计：

\[ C(a,b) = \sum_{w} c(w)\cdot \#\{i: s_i^{(w)}=a,\ s_{i+1}^{(w)}=b\}. \]

这件事很重要：真实 tokenizer 训练通常先把巨大 corpus 压成 tokenized word inventory 和 count，再在这个压缩表示上反复更新 pair counts。否则每轮直接扫原始几十 TB 文本是不现实的。

ImportantTheorem: A BPE Merge Reduces Corpus Length by Its Weighted Pair Count

For a corpus represented as symbol sequences with weighted adjacent-pair count \(C(a,b)\), replacing every non-overlapping occurrence of pair \((a,b)\) by a new symbol reduces the total symbol count by exactly the number of replaced occurrences.

NoteProof

每次把相邻两个 symbol \((a,b)\) 替换为一个 symbol \(ab\)，该位置的 symbol 数从 \(2\) 变成 \(1\)，长度减少 \(1\)。若在整个加权 corpus 中实际替换了 \(M\) 个 non-overlapping occurrence，总长度就减少 \(M\)。

通常写 \(C(a,b)\) 是因为 pair occurrence 不重叠时 \(M=C(a,b)\)；若 pair 会自重叠，例如 a a a 中的 (a,a)，一次 merge 只能替换其中一个 non-overlapping occurrence，所以实现里必须按序扫描，而不能只看裸频数公式。

所以 BPE 的“高频 pair”并不是语言学上最有意义的 pair，而是当前符号表示里最能减少序列长度的 pair。它是 compression prior，不是 morphology parser。

Encoding Algorithm

朴素 encoder：

def encode_word(symbols, merge_rank):
    symbols = list(symbols)
    while True:
        pairs = [(symbols[i], symbols[i + 1]) for i in range(len(symbols) - 1)]
        ranked = [(merge_rank[p], p) for p in pairs if p in merge_rank]
        if not ranked:
            return symbols
        _, best = min(ranked)
        symbols = merge_pair(symbols, best)

关键点：

1. encoding 只查 merge rank，不重新统计文本频率；
2. merge 是 greedy，不求全局最短分词；
3. 合并一个 pair 会改变左右邻居 pair，所以高效实现不能每轮全量扫描。

WarningPitfall: BPE Is Greedy, Not Globally Optimal

BPE encoding follows learned merge ranks greedily. It does not solve a global shortest-token segmentation problem for each input.

Reference Trainer

最小 BPE trainer 可以写成下面这样。为了突出算法，这里用词尾 </w>，没有加入 byte-level、normalizer 和 pretokenizer。

from collections import Counter, defaultdict


def word_to_symbols(word):
    return tuple(word) + ("</w>",)


def pair_counts(vocab):
    counts = defaultdict(int)
    for symbols, freq in vocab.items():
        for a, b in zip(symbols, symbols[1:]):
            counts[(a, b)] += freq
    return counts


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


def train_bpe(words, num_merges):
    vocab = Counter(word_to_symbols(w) for w in words)
    merges = []
    for rank in range(num_merges):
        counts = pair_counts(vocab)
        if not counts:
            break
        best = max(counts, key=counts.get)
        merges.append((best, rank))
        next_vocab = Counter()
        for symbols, freq in vocab.items():
            next_vocab[merge_symbols(symbols, best)] += freq
        vocab = next_vocab
    return dict(merges), vocab

这段代码揭示了几个真实实现必须处理的点：

1. vocab 的 key 是 symbol tuple，不是字符串，否则合并后很难无歧义地拆回 symbol；
2. pair count 要乘以 word/corpus frequency；
3. merge 时必须线性扫描，避免自重叠 pair 被重复替换；
4. merges 的顺序就是之后 encoder 的 priority。

Reference Encoder

训练得到 merge_rank 后，推理时不再看 corpus frequency，只看 rank：

def bpe_encode_piece(piece, merge_rank):
    symbols = tuple(piece)
    while len(symbols) >= 2:
        pairs = [(symbols[i], symbols[i + 1]) for i in range(len(symbols) - 1)]
        candidates = [(merge_rank[p], p) for p in pairs if p in merge_rank]
        if not candidates:
            break
        _, best = min(candidates)
        symbols = merge_symbols(symbols, best)
    return symbols

为什么用 min(rank)？因为 rank 越小表示越早学到，优先级越高。若同一个输入里有多个可合并 pair，encoder 选择 rank 最小的 pair，然后把所有 non-overlapping occurrences 合并，再进入下一轮。

这也是 vocab.json 和 merges.txt 必须匹配的原因。vocab 给最终 symbol 分配 id；merges 定义如何从底层 symbol 走到最终 symbol。两者错配时，round-trip decoding 可能还能产出字符串，但 token ids 已经不是训练时的离散空间。

Efficient Implementation

若每轮扫描全字符串，长度 \(n\) 的输入最坏是 \(O(n^2)\)。实际 tokenizer 通常维护：

• symbol linked list；
• pair 到 rank 的 hash map；
• pair priority queue；
• merge 后只更新左右邻居 pair。

这样复杂度接近：

\[ O(n\log n), \]

再加上 Rust/C++ 实现、cache 和 batch 并行，才支撑大规模数据预处理。

更工程化一点，可以把一个 pretokenized piece 看成 linked list：

node0 <-> node1 <-> node2 <-> ... <-> node{n-1}

priority queue 中存 (rank, left_node_id, right_node_id)。每次弹出 rank 最小的 pair 时，要检查这两个 node 是否仍然相邻；如果中途被别的 merge 改掉，就丢弃 stale entry。成功 merge 后，只需要重新插入新 node 左右两侧形成的新 pair。

WarningPitfall: Fast BPE Needs Stale-Pair Checks

Priority-queue BPE implementations produce stale pair candidates after local merges. A candidate popped from the queue must be validated against the current linked-list state before applying it.

实际 serving 中还会给常见 piece 做 cache：

\[ \operatorname{cache}[\text{piece}] \mapsto (\text{token ids},\text{offsets}). \]

这就是为什么 tokenizer 在长 prompt、重复模板、批量请求中通常是 CPU hot path：模型还没上 GPU，CPU 已经在做 UTF-8、regex、hash lookup、merge、offset bookkeeping。

Production Pair-Count Trainer

上面的 trainer 每一轮都重新扫描整个 vocabulary，适合教学，但不适合训练十万级 merges。真实 BPE trainer 的核心问题是：一次 merge 只会改变被 merge 位置附近的 pair count，不应该让所有 word types 重新计数。

把 pretokenized corpus 压缩成加权 word types：

raw corpus
-> pretokenized pieces
-> Counter[piece] = frequency
-> tuple symbols with frequency

例如：

low:    5
lower:  2
lowest: 1

不是展开成 8 个样本，而是保留 type frequency。pair count 因此是 weighted count：

\[ C(a,b) = \sum_{w} c(w) \sum_{i=1}^{|w|-1} \mathbf{1}[(s_i^{(w)},s_{i+1}^{(w)})=(a,b)]. \]

第一次统计后，维护三类状态：

State	Meaning	Why needed
words[id]	当前 symbol linked list	merge 后 local rewrite
pair_count[pair]	当前全局 weighted pair count	choose next merge
pair_pos[pair]	pair 出现在哪些 word/position	update affected locations

一次 merge (a,b)->ab 的局部更新逻辑是：

... left, a, b, right ...

替换前减少：

(left, a), (a, b), (b, right)

替换后增加：

(left, ab), (ab, right)

计数变化都要乘以这个 word type 的 frequency。也就是说，高效 trainer 的本质不是“更快地找最大 pair”这么简单，而是维护一个会随局部重写变化的动态多重图。

NoteInvariant: Pair Counts Must Match Current Symbols

After every merge, pair_count must equal the weighted adjacent-pair counts of the current symbolized vocabulary. A stale count silently changes the learned merge order.

一个堆实现通常不会在每次 pair count 改变时删除旧堆元素，而是插入新元素并在 pop 时验证：

import heapq


def push_pair(heap, pair, count, version):
    # Python heap is min-heap, so use negative count.
    heapq.heappush(heap, (-count, version[pair], pair))


def pop_best_valid(heap, pair_count, version):
    while heap:
        neg_count, seen_version, pair = heapq.heappop(heap)
        if seen_version != version[pair]:
            continue
        if -neg_count != pair_count[pair]:
            continue
        return pair
    return None

这里的 version[pair] 是 stale-entry 检查。没有它，堆里旧的高频 pair 可能在已经被局部 merge 改写后再次被选中，得到一个不可复现的 merge table。

Trainer Tie-Breaks

当两个 pair frequency 完全相同，trainer 必须有 deterministic tie-break。常见做法是按 pair 的字典序、首次出现顺序或内部 id 排序。这个细节看起来很小，但会改变 merge rank：

rank 100: ("a", "b")
rank 101: ("b", "c")

和

rank 100: ("b", "c")
rank 101: ("a", "b")

可能让同一句输入得到不同 token ids。对于 LLM checkpoint 来说，token id 不是可交换标签；embedding row 和 LM head row 已经绑定了训练语义。

WarningPitfall: Re-Training a Similar Tokenizer Is Not Compatible

Even if two tokenizers have the same vocabulary size and visually similar tokens, different merge ranks or ids produce a different discrete space. A pretrained checkpoint cannot be safely reused without the exact tokenizer files.

Byte-Level BPE

GPT-2 和 Qwen 系列都采用 byte-level BPE 思路。底层 alphabet 不是字符，而是 256 个 byte。任意 Unicode 字符串先转成 UTF-8 bytes：

"你" -> e4 bd a0

再在 byte 序列上应用 BPE merge。这样不会出现 OOV，因为任意字符串都能分解成 bytes。

NoteDefinition: Byte-Level BPE

Byte-level BPE starts from the 256 byte values and learns merge rules over byte sequences. It combines byte-level coverage with subword-level compression.

为什么不直接用 byte token？因为序列太长。BBPE 让常见 byte 序列合并成常见 subword，从而缩短上下文。

Byte-to-Unicode Mapping

GPT-2 风格 BBPE 有一个实现细节：为了让 BPE 在“字符串 symbol”上工作，它会把 byte 映射到一组可打印 Unicode 字符，避免控制字符、空白符直接破坏 regex 和文件格式。

抽象地说，有一个双射：

\[ \phi:\{0,\ldots,255\}\rightarrow\mathcal{U}. \]

encoding：

\[ \text{string} \rightarrow \text{UTF-8 bytes} \rightarrow \phi(\text{bytes}) \rightarrow \text{BPE merges} \rightarrow \text{token ids}. \]

decoding：

\[ \text{token ids} \rightarrow \text{BPE symbols} \rightarrow \phi^{-1} \rightarrow \text{bytes} \rightarrow \text{UTF-8 string}. \]

这就是 BBPE 能无损表示任意文本的原因。

下面是 GPT-2 风格 byte-to-Unicode map 的最小形态。它保留一部分可打印字符，再给剩余 byte 分配额外 Unicode code point：

def bytes_to_unicode():
    bs = list(range(ord("!"), ord("~") + 1))
    bs += list(range(ord("¡"), ord("¬") + 1))
    bs += list(range(ord("®"), ord("ÿ") + 1))
    cs = bs[:]
    n = 0
    for b in range(256):
        if b not in bs:
            bs.append(b)
            cs.append(256 + n)
            n += 1
    return {b: chr(c) for b, c in zip(bs, cs)}

如果不做这一步，byte 32 的空格、换行、控制字符会在 regex、文本文件、JSON 序列化里产生各种歧义。byte-level BPE 的“byte”并不是直接把不可见 byte 写进 merges 文件，而是通过这个双射把 byte 暂时伪装成普通 symbol。

Pretokenization and Whitespace

实际 BPE 通常先 pretokenize，再对每个片段内部做 merge。GPT-2 风格 pretokenization 会把空格和后续词绑定：

"hello world" -> "hello" | " world"

因此 "word" 和 " word" 往往是不同 token。许多可视化工具用 Ġ 表示前导空格：

hello | Ġworld

WarningPitfall: Whitespace Is Semantic to the Tokenizer

For byte-level BPE tokenizers, leading whitespace often changes token identity. "word" and " word" may map to different token ids.

这对 prompt engineering、代码缩进、markdown 列表尤其重要。模型不是在抽象 word 上推理，而是在这些具体 token id 上推理。

Full Tokenizer Pipeline

现代 tokenizer 通常不是一个函数，而是一条 pipeline：

\[ \text{raw string} \xrightarrow{\text{normalizer}} \text{normalized string} \xrightarrow{\text{pretokenizer}} \text{pieces} \xrightarrow{\text{model}} \text{tokens} \xrightarrow{\text{postprocessor}} \text{input ids}. \]

各层职责不同：

Stage	Role	Example failure
normalizer	Unicode normalization, case handling, cleanup	full-width/half-width drift
pretokenizer	split raw text into merge regions	whitespace or code indentation changes
model	BPE/WordPiece/Unigram segmentation	wrong merge table or vocab
postprocessor	add BOS/EOS/role tokens	chat template mismatch
decoder	map ids back to text	byte fallback or special-token leak

GPT-2 风格 byte-level BPE 的 normalizer 很轻，主要依赖 byte fallback 保证覆盖；BERT 风格 WordPiece 常见 lower-case、accent stripping 和 ## continuation；SentencePiece 常把 normalization 和 pretokenization 都封装进同一个 model 文件。

Offset Mapping

训练、评测和 UI 高亮常需要知道 token 对应原字符串哪一段。tokenizer 因此会返回：

{
    "input_ids": [15496, 995],
    "attention_mask": [1, 1],
    "offset_mapping": [(0, 5), (5, 11)],
}

offset 的难点在于 normalizer 和 byte mapping 会改变中间表示。若 "é" 被 normalize 成 "e" 加 combining mark，或者中文字符被转成 3 个 UTF-8 bytes，token offset 必须仍然指回原始字符串位置。这是实现 tokenizer 可解释性、NER span alignment 和数据清洗时最容易出 bug 的地方。

Pretokenizer Regex and Added-Token Priority

很多 tokenizer bug 不是发生在 BPE merge 表，而是发生在 merge 之前。以 GPT-2 风格为例，pretokenizer 先用 regex 把原文切成 pieces，然后每个 piece 内部独立做 byte-level BPE。一个简化的切分意图是：

text -> words with optional leading space
     -> numbers
     -> punctuation
     -> whitespace runs

这意味着 BPE 从来不会跨 pretokenizer boundary 合并。若 regex 把 "don't" 切成 "don" 和 "'t"，那么 tokenizer 可以学到 "'t"，但不会学到跨边界的 "n't"；若 regex 把前导空格放进 word piece，" cat" 和 "cat" 就进入两套不同的 pair statistics。

NoteDefinition: Pretokenization Boundary

A pretokenization boundary is a hard boundary across which the tokenizer model is not allowed to merge symbols. It changes the candidate segmentations before BPE ranks are applied.

special tokens 和 added tokens 通常又比 regex 更早被识别。实际 pipeline 更像：

raw text
-> scan added/special tokens atomically
-> apply normalizer to ordinary spans
-> pretokenize ordinary spans
-> byte map and BPE encode each piece
-> concatenate ids

如果 <|assistant|> 是 added token，它必须先被整体吃掉，而不是被 normalizer 改写或被 regex 切成 <, |, assistant, |, >。一个常见实现是把 added tokens 放入 trie：

class AddedTokenTrie:
    def __init__(self, tokens):
        self.root = {}
        for token, token_id in tokens.items():
            node = self.root
            for ch in token:
                node = node.setdefault(ch, {})
            node["$"] = token_id

    def longest_match(self, text, start):
        node = self.root
        best = None
        pos = start
        while pos < len(text) and text[pos] in node:
            node = node[text[pos]]
            pos += 1
            if "$" in node:
                best = (pos, node["$"])
        return best

encoding 时从当前位置取 longest added-token match；若没有 match，才把普通 span 交给 normalizer/pretokenizer。这个优先级决定了 chat template 是否稳定。

WarningPitfall: Added Tokens Can Shadow Ordinary Text

An added token such as <tool> is matched before ordinary BPE. If the same literal string appears in user content, the tokenizer may treat it as protocol unless the template escapes or disallows it.

这就是 tool calling、HTML-like tags、thinking tags 需要 escaping policy 的原因。否则用户输入里手写一个 </think>，模型和 parser 可能把它当成协议边界，而不是普通文本。

Added-Token Scanner with Offsets

实际 encoder 通常不是直接调用 longest_match 然后把 id 拼起来。它需要先把 raw text 切成两类 span：

Span type	Encoded by	Offset behavior
added/special token	direct id lookup	whole literal interval
ordinary text	normalizer + pretokenizer + BPE	projected back to original chars

NoteDefinition: Added-Token Span

An added-token span is a raw-text interval that is consumed atomically and mapped directly to a tokenizer id before normal normalization, pretokenization, and BPE segmentation.

leftmost-longest 规则可以形式化为：在当前位置 \(i\)，若存在多个 added token literal 匹配原文前缀，选择结束位置最大的那个：

\[ j^\star = \arg\max_j \{j:\text{text}[i:j]\in\mathcal{A}\}. \]

若没有匹配，则当前位置进入 ordinary span，直到下一个 added token 开始。

一个更完整的 scanner 会返回 span 和 offset：

from dataclasses import dataclass


@dataclass(frozen=True)
class ScanSpan:
    kind: str          # "added" or "ordinary"
    text: str
    left: int
    right: int
    token_id: int | None = None


def scan_added_tokens(text, trie):
    spans = []
    ordinary_start = 0
    i = 0
    while i < len(text):
        match = trie.longest_match(text, i)
        if match is None:
            i += 1
            continue

        end, token_id = match
        if ordinary_start < i:
            spans.append(ScanSpan("ordinary", text[ordinary_start:i], ordinary_start, i))
        spans.append(ScanSpan("added", text[i:end], i, end, token_id))
        i = end
        ordinary_start = i

    if ordinary_start < len(text):
        spans.append(ScanSpan("ordinary", text[ordinary_start:], ordinary_start, len(text)))
    return spans

然后 ordinary span 才进入 normalizer/pretokenizer/BPE。关键是 offset 要加回 span 的起点：

def encode_with_added_tokens(text, trie, encode_ordinary):
    input_ids = []
    offsets = []

    for span in scan_added_tokens(text, trie):
        if span.kind == "added":
            input_ids.append(span.token_id)
            offsets.append((span.left, span.right))
            continue

        pieces = encode_ordinary(span.text)  # returns (ids, local_offsets)
        for token_id, (l, r) in pieces:
            input_ids.append(token_id)
            offsets.append((span.left + l, span.left + r))

    return input_ids, offsets

ImportantTheorem: Atomic Added Tokens Cannot Be Split by BPE

If added-token spans are removed from the ordinary text stream before pretokenization, no later BPE merge or split can change their internal tokenization.

NoteProof

scanner 把原文分成互不重叠的 intervals。对于 added-token interval \([i,j)\)，encoder 直接追加对应 id：

\[ \text{id}(\text{text}[i:j]). \]

后续 normalizer、pretokenizer 和 BPE 只作用在 ordinary spans 上。由于 added-token interval 不进入 ordinary stream，它不会产生字符、byte symbol 或 pair candidate。因此 BPE 既不能拆分它，也不能和它左右两侧的 ordinary text 跨边界 merge。

这个性质解释了为什么 added token 的位置必须在 pipeline 前面。若先 normalize 或 regex split，再识别 <|assistant|>，就可能出现：

< | assistant | >

这种拆分，chat template 的 role boundary 直接失效。

Escaping Protocol Tokens in User Text

added token 的优先级也带来安全/数据问题：协议 token literal 出现在用户内容里时，encoder 会把它当协议，而不是普通文本。一个 SFT renderer 应该有 escaping policy。常见方案包括：

Policy	Example	Trade-off
reject	disallow raw <|assistant|> in user content	simple but strict
escape	replace < with escaped form	preserves content but changes text
quote span	wrap user content in a format parser understands	needs robust parser
use out-of-band roles	store roles separately until final trusted render	safest for training pipelines

一个最小检测函数：

def assert_no_unescaped_added_tokens(user_text, added_literals):
    hits = [tok for tok in added_literals if tok in user_text]
    if hits:
        raise ValueError(f"user content contains reserved tokenizer literals: {hits}")

真实系统更常做“模板渲染前检查结构化 messages”，而不是渲染成字符串后再猜哪些 token 来自用户。否则 assistant span、tool span、thinking span 的 offset 都可能被用户注入的 literal 打乱。

WarningPitfall: Atomicity Is Not Authorization

Recognizing <|tool|> as one token only means the tokenizer consumes it atomically. It does not prove the token came from a trusted template position. Training and serving code must still distinguish protocol text from user-supplied text.

added-token smoke tests 应该同时检查 id 和 offset：

def assert_added_token_atomicity(tokenizer, text, literal, token_id):
    enc = tokenizer(text, add_special_tokens=False, return_offsets_mapping=True)
    ids = enc["input_ids"]
    offsets = enc["offset_mapping"]
    pos = text.index(literal)
    expected = (pos, pos + len(literal))

    matched_offsets = [
        tuple(off)
        for tid, off in zip(ids, offsets)
        if tid == token_id
    ]
    assert matched_offsets == [expected]

如果同一个 literal 在 user content 和 template control position 都可能出现，单靠这个测试还不够；还要测试 renderer 是否拒绝或 escape 用户内容里的 reserved literal。

Offset Mapping as Interval Algebra

offset mapping 最好按区间代数思考，而不是按 token 字符串思考。给定原文字符区间 \([l_i,r_i)\) 和目标 span \([a,b)\)，判断 token 是否覆盖 span 的条件是：

\[ \max(l_i,a)<\min(r_i,b). \]

这叫 half-open interval overlap。它比“token decoded string 是否在 answer 中”可靠，因为 decoded token 可能包含前导空格、byte fallback 字符、normalization 后的组合字符，甚至空字符串 special token。

NER、SFT span mask、tool-call argument mask 都应从原始字符 span 出发，再映射到 token span：

def overlap(token_span, target_span):
    left, right = token_span
    start, end = target_span
    return max(left, start) < min(right, end)


def mask_from_spans(offsets, spans):
    out = []
    for offset in offsets:
        train = any(overlap(offset, span) for span in spans)
        out.append(train)
    return out

如果 normalizer 会改写字符串，好的 tokenizer 实现会维护 alignment table：

original chars -> normalized chars -> bytes -> bpe symbols -> token ids

每一步都要能把区间投回上一步。否则看似只是“分词器输出”，实际会破坏监督标签。

Special Tokens

LLM tokenizer 还包含 special tokens，它们不是从文本频率自然 merge 出来的，而是协议符号：

Special token	Typical role
<bos>	sequence start
<eos>	sequence end / stopping
<pad>	batching
role tokens	system/user/assistant boundary
tool tokens	function-call boundary
thinking tags	reasoning trace boundary

special token 的要求是：encoding 时必须整体识别，不能被拆成普通字符。例如一个 reasoning 模型若把 </think> 当成特殊 token，就应该整体映射到一个 id，而不是拆成 <, /, think, >。

Qwen3 technical report 写明它使用 Qwen tokenizer，即 byte-level BPE，vocabulary size 为 \(151{,}669\)。官方博客示例还通过 </think> token 分离 thinking content 和 final content。这说明 tokenizer 同时承载压缩、对话格式和推理协议。

Added Tokens and Embedding Resize

给 tokenizer 增加 special tokens 不只是改 tokenizer 文件。模型 embedding 和 LM head 也要能覆盖新增 id：

num_added = tokenizer.add_special_tokens(
    {"pad_token": "<|pad|>", "additional_special_tokens": ["</think>"]}
)
model.resize_token_embeddings(len(tokenizer))

若模型使用 tied embeddings，则输入 embedding 和输出 LM head 通常共享权重：

\[ \ell_t = h_t E^\top, \]

其中 \(E\in\mathbb{R}^{|\mathcal{V}|\times d}\)。新增 token 会改变 \(|\mathcal{V}|\)，因此必须 resize。否则常见错误包括 index out of range、special token 永远不会被预测、或者 padding token 参与 loss。

WarningPitfall: Pad Token Is a Training Decision

Adding a pad token changes batching behavior and sometimes the vocabulary. If labels are not masked at pad positions, the model is trained to predict padding.

右 padding 和左 padding 的差异：

Scenario	Common padding side	Reason
training with full attention mask	right padding	labels align naturally
decoder-only batched generation	left padding	last non-pad token aligns across batch
encoder-only classification	either, usually right	pooled representation handles mask

GPT-2 原始 tokenizer 没有独立 pad token，很多实践会设 pad_token=eos_token。这可以让 batching 跑起来，但必须保证 loss mask 不把 padding position 当作真实 EOS 学习。

Tokenization Changes the Objective

causal LM loss 是 token-level：

\[ \mathcal{L} = \frac{1}{T} \sum_{t=1}^{T} -\log p_\theta(x_t\mid x_{<t}). \]

如果同样的原始文本在某语言中被切成更多 token，那么它会产生更多训练位置，也消耗更多上下文长度和 attention FLOPs。常用 fertility 衡量压缩率：

\[ \operatorname{fertility}(s) = \frac{\#\text{tokens}}{\#\text{words or characters}}. \]

多语言 LLM 的 tokenizer 设计必须关心 fertility，否则某些语言会在同样 context budget 下天然吃亏。

BPE vs. WordPiece vs. Unigram

Method	Training idea	Encoding idea	Typical models
BPE	merge frequent adjacent pairs	greedy merge by rank	GPT-2, Qwen
WordPiece	choose merges improving likelihood	greedy longest match	BERT
Unigram LM	learn probabilistic token inventory	choose likely segmentation	SentencePiece models

BPE 简单、快、可复现；缺点是 greedy merge 不保证语义最优。Unigram 可以表达多个候选 segmentation 的概率，但训练和实现更复杂。

WordPiece

WordPiece 也从小单位构造 subword vocabulary，但它的 merge 选择通常不是裸 pair frequency，而是偏向能提升语言模型 likelihood 的组合。直觉上，一个常见近似 score 是：

\[ \operatorname{score}(a,b) \approx \frac{C(a,b)}{C(a)C(b)}. \]

这个分数会惩罚单独已经很常见的 symbol，鼓励合并“强绑定”的 pair。BERT 风格 WordPiece 还用 ## 标记 continuation：

unaffable -> un ##aff ##able

encoding 时通常做 longest-match-first：从当前位置开始，找 vocabulary 中最长可匹配 token；如果不是词首，就要求 token 带 ##。找不到则退到 [UNK]。这和 byte-level BPE 的无 OOV 性质不同。

Unigram LM

Unigram tokenizer 把 segmentation 当成隐变量。给定 token vocabulary \(\mathcal{V}\) 和 token probability \(p(u)\)，字符串 \(s\) 的概率是所有 segmentation 的边缘和：

\[ p(s) = \sum_{z\in\mathcal{Z}(s)} \prod_{u\in z}p(u). \]

训练时用 EM 估计 token probabilities，并逐步裁剪贡献小的 token。编码时可以选择最大概率 segmentation：

\[ z^\star = \arg\max_{z\in\mathcal{Z}(s)} \sum_{u\in z}\log p(u), \]

这可以用 Viterbi 动态规划求解。Unigram 的优势是 segmentation 有概率语义，也容易做 subword regularization；缺点是训练和实现比 BPE 更重。

NoteDefinition: Subword Regularization

Subword regularization samples from multiple plausible segmentations during training instead of always using a deterministic best segmentation.

对模型来说，这相当于给输入离散化过程加噪声。它可能提升鲁棒性，但也会让训练数据 pipeline 更难复现。

Worked Example

假设 merge table：

("l", "o")     rank 0
("lo", "w")    rank 1
("e", "r")     rank 2
("low", "er")  rank 3

encoding lower：

l o w e r
lo w e r
low e r
low er
lower

若输入 lowest，但没有 low + est 的 merge，可能停在：

low e s t

所以 BPE 学到的是训练语料里的频率结构，不是词典规则或词法规则。

再看一个和空格相关的例子。假设 byte-level pretokenizer 把前导空格保留进 piece：

"hello world" -> ["hello", " world"]
"world"       -> ["world"]

那么训练时 " world" 和 "world" 的 pair 统计是分开的。高频英文语料里，带前导空格的词非常常见，因此 tokenizer 往往有一个 token 表示 " world"，却不一定有同样 rank 的 "world"。这解释了为什么同一个词放在句首和句中会有不同 tokenization，也解释了 prompt 模板里多一个空格会改变模型看到的离散序列。

From Tokenizer Output to Model Tensors

最终训练 batch 至少包含三种张量：

enc = tokenizer(
    texts,
    padding=True,
    truncation=True,
    return_offsets_mapping=True,
)

input_ids = enc["input_ids"]
attention_mask = enc["attention_mask"]
offsets = enc["offset_mapping"]

对 decoder-only LM，attention_mask 和 causal mask 会合成：

\[ M_{ij} = \mathbf{1}[j\leq i]\cdot \mathbf{1}[\text{token }j\text{ is not pad}]. \]

loss mask 又是另一件事：

\[ m_i^{\text{loss}} = \mathbf{1}[\text{label at }i\text{ is trainable}]. \]

这三个东西不要混在一起：

Tensor	Controls	Common bug
input_ids	embedding lookup	token ids from wrong tokenizer
attention_mask	what positions can be attended	pad tokens leak into context
labels == -100	what positions contribute loss	user/pad tokens trained as targets
offset_mapping	original text span alignment	normalized/byte offsets point to wrong chars

一个 tokenizer 改动如果没有同步更新这四个层面，通常不会立刻报错，而是在训练数小时后表现成 loss 异常、chat template 失效或 span 对齐错误。

Chat Template to Training Labels

instruction tuning 里最容易被低估的 tokenizer 问题，是如何从结构化消息得到 input_ids、attention_mask 和 labels。假设一条样本是：

messages = [
    {"role": "system", "content": "You are concise."},
    {"role": "user", "content": "Explain BPE."},
    {"role": "assistant", "content": "BPE repeatedly merges frequent adjacent symbols."},
]

chat template 先把它序列化成一个普通字符串：

<|system|>
You are concise.
<|user|>
Explain BPE.
<|assistant|>
BPE repeatedly merges frequent adjacent symbols.<|end|>

然后 tokenizer 才把字符串转成 ids。关键是：assistant answer 的字符区间必须被映射回 token 区间，才能构造 loss mask。形式化地说，template 给出若干可训练字符 span：

\[ \mathcal{S} = \{[a_k,b_k): k=1,\ldots,K\}, \]

tokenizer 给出 token offset：

\[ o_i=[l_i,r_i). \]

一个 token 是否训练，取决于它的原文 span 是否落在 assistant answer 内：

\[ m_i^{\text{loss}} = \mathbf{1}\left[ \exists k,\ [l_i,r_i)\cap[a_k,b_k)\neq\emptyset \right]. \]

这一步不是 decoration，而是在定义 SFT objective。prompt token 仍然进入上下文，但不进入 loss；assistant token 既进入上下文，也作为预测目标。

def build_chat_example(tokenizer, messages):
    text, spans = render_chat_with_assistant_spans(messages)
    enc = tokenizer(
        text,
        add_special_tokens=False,
        return_offsets_mapping=True,
    )

    labels = [-100] * len(enc["input_ids"])
    for i, (left, right) in enumerate(enc["offset_mapping"]):
        train = any(max(left, a) < min(right, b) for a, b in spans)
        if train:
            labels[i] = enc["input_ids"][i]

    return {
        "input_ids": enc["input_ids"],
        "attention_mask": [1] * len(enc["input_ids"]),
        "labels": labels,
    }

这里先把 labels[i] 设置成同位置 token id，是因为许多 decoder-only model 会在 forward 内部做 one-token shift。若你的训练 step 显式切 logits[:, :-1] 和 labels[:, 1:]，就不能再依赖模型内部 shift。两种写法只能选一种。

WarningPitfall: Offset Masks Break Under Template Drift

If the template used to record assistant spans differs from the template passed to the tokenizer, role masks can shift by several tokens while tensor shapes remain valid.

真实系统中还要决定 padding side。右 padding 更适合训练，因为 token 顺序直观，最后若干位置是 pad：

ids:    [BOS, user, assistant, answer, EOS, PAD, PAD]
mask:   [1,   1,    1,         1,      1,   0,   0]
labels: [-100,-100,-100,       ans,    eos, -100,-100]

左 padding 更适合 batched generation，因为每个样本的最后一个非 pad token 可以对齐到同一列，便于取 next-token logits：

ids:    [PAD, PAD, BOS, user, assistant]
mask:   [0,   0,   1,   1,    1]
next:                         ^

如果一个 decoder-only 模型用 absolute position embedding，左 padding 还必须重算 position_ids，让第一个非 pad token 的位置从 \(0\) 开始：

\[ \operatorname{position\_id}_{b,t} = \max\left(0,\sum_{j\leq t}\operatorname{attention\_mask}_{b,j}-1\right). \]

RoPE 模型也需要正确的 cache offset；否则 prefill 和 decode 阶段看到的位置相位不一致。很多“padding side 不重要”的说法只在 attention mask、loss mask、position ids 和 cache offsets 全部处理正确时才成立。

Tokenizer Artifact Manifest

一个可复现 checkpoint 不应该只写“使用 Qwen tokenizer”或“使用 GPT-2 tokenizer”。至少要把 tokenizer artifact 当成模型权重的一部分做 hash：

Artifact	What it fixes
tokenizer.json	normalizer, pretokenizer, model, postprocessor, decoder
vocab.json / merges.txt	BPE ids and merge ranks when split files are used
special_tokens_map.json	BOS/EOS/PAD/UNK and role-token mapping
tokenizer_config.json	padding side, model max length, chat template
chat_template	role serialization and generation prompt
added-token table	atomic protocol/tool/thinking tokens

manifest 可以写成：

{
  "tokenizer_sha256": "...",
  "vocab_size": 151669,
  "bos_token_id": 151643,
  "eos_token_id": 151645,
  "think_end_id": 151668,
  "padding_side_train": "right",
  "padding_side_generate": "left",
  "chat_template_sha256": "..."
}

这些字段不是文档洁癖，而是 debug 信息。若 fine-tuning 后模型表现为“会说话但格式怪、tool call 经常漏括号、thinking tag 乱飞”，第一批要比对的就是 tokenizer 和 template manifest。

NoteDefinition: Tokenizer-Checkpoint Compatibility

A tokenizer is compatible with a checkpoint only if token ids, special-token ids, merge ranks, normalizer, pretokenizer, postprocessor, and chat template semantics match the training-time artifacts.

Tokenizer Throughput and Cache Boundaries

训练大模型时，tokenizer 往往离 GPU 很远：它可能在数据准备阶段离线跑，也可能在在线 serving 的 CPU path 上跑。两种场景的优化目标不同：

Scenario	Hot path	Cache key
offline pretraining	corpus streaming and sharding	document id + tokenizer version
SFT packing	chat template rendering + span masks	message json + template hash
online serving	prompt template + UTF-8 + BPE	rendered prompt string + tokenizer hash
repeated system prompt	prefix ids and KV prefill	system/template prefix hash

BPE cache 不能只按 raw text 做 key，还要包含 normalizer、added tokens、chat template 和 special-token policy。否则升级模板后复用旧 cache，会得到“看似合法但语义过期”的 input_ids。

一个安全 cache key 至少包含：

cache_key = (
    tokenizer_hash,
    chat_template_hash,
    add_special_tokens,
    truncation_side,
    text,
)

如果返回 offset_mapping 或 labels，cache key 还必须包含 span-rendering policy，因为同一段 text 可以对应不同的可训练 token mask。

Engineering Checklist

训练或替换 tokenizer 时，至少要检查：

1. Round-trip: decode(encode(x)) == x 是否对 Unicode、emoji、代码、换行成立；
2. Special-token atomicity: <|assistant|>、</think>、tool tags 是否整体成 token；
3. Fertility: 中文、英文、代码、数学公式的 tokens/char 或 tokens/word；
4. Template compatibility: chat template 产生的 role boundary 是否和 SFT 数据一致；
5. Reserved literal policy: 用户内容里的 protocol token literal 是否被 reject/escape；
6. Padding mask: attention_mask 和 labels == -100 是否覆盖 pad positions；
7. Vocab/merge hash: vocab.json、merges.txt、tokenizer.json 是否和 checkpoint 同版本；
8. Embedding size: len(tokenizer) 是否等于 model embedding rows；
9. Offset mapping: span task 和 UI 高亮是否能回到原文位置；
10. Throughput: tokenizer 是否成为 prefill 前的 CPU bottleneck；
11. Determinism: normalizer、pretokenizer、added tokens 和 sampling/dropout 设置是否固定。

最小 smoke test：

samples = [
    "hello world",
    "  indented code\n    x = 1",
    "中文和English混合",
    "emoji: 🧠🚀",
    "<|user|> hi </think>",
]

for s in samples:
    ids = tokenizer.encode(s, add_special_tokens=False)
    assert tokenizer.decode(ids) == s

这类测试看似朴素，却能抓住 tokenizer 中最昂贵的错误：训练数据和推理服务看到的 token 序列不是同一个世界。

References

• Language Models are Unsupervised Multitask Learners, Radford et al.
• Qwen3 Technical Report, Qwen Team.
• Qwen3 official blog, Qwen Team.