w wyl123ly 的博客
MD

字节对编码BPE原理

24 KB 2026.10.22 原文件

字节对编码BPE原理

定义

字节对编码(Byte Pair Encoding,BPE)是一种子词分词算法:以 256 个字节值为基础符号,在预切分后的语料上反复统计相邻符号对的出现频次、把频次最高的符号对合并为一个新符号,并把合并顺序记录为有序表,词表由基础符号、合并产物与特殊 token 三部分构成。

本篇符号约定如下。

符号含义
基础符号集,字节级下为
训练语料,元素为预切分后的片段及其出现次数
片段 的出现次数
相邻符号对 在整份语料中的加权频次
合并表, 是第 次合并的符号对
合并次数
、词表与词表大小,, 为特殊 token 集
合并产物 的 rank,即它是第几次合并的产物
压缩率,, 为字节数, 为 token 数
pattern预切分正则,决定哪些相邻字节可以被合并

其余术语在首次出现处定义:预切分(pretokenization)指在合并统计之前用正则把文本切成互不跨界的片段;合并序指 中规则的先后,它同时是 BPE 的编码顺序;rank 是 tiktoken 对合并序的数值化表示,rank 越小表示越早学到;贪心合并指编码时反复合并当前可合并对中 rank 最小者,直到没有合法对。

为什么重要

BPE 是词表的生产过程,而词表是模型参数的组成部分。nanochat 的词表 32768 由三部分相加得到:256 个单字节符号、32503 个合并产物、9 个特殊 token。合并次数 32503 不是超参数之外的细节,它直接决定了 wte 与 lm_head 的行数,也决定了同一段文本的 token 数。

三项后果可以量化。第一,压缩率决定序列长度:例 1 的语料 36 字节经 7 次合并后为 11 个 token,;若无合并则 ,注意力计算量按 倍增长。第二,压缩率与词表大小存在边际递减:每个合并只能缩短它所匹配的符号对,越往后匹配次数越少,因此 tok_train.py 用 2B 字符训练 32503 次合并时,后段合并的收益显著低于前段。第三, 通过 bpb 进入评测,见 为什么需要分词。

BPE 还决定了两件容易忽略的工程事实。其一,训练与推理必须共享同一个 pattern:train_from_iterator 训练时把 SPLIT_PATTERN 交给 rustbpe,随后用 tokenizer.get_pattern() 把同一个 pattern 写进 tiktoken.Encoding,二者不一致会导致切分边界不同、压缩率静默下降。其二,BPE 不识别语言学边界:它只按相邻字节对的频次合并,因此「哪些字符串能成为一个 token」是统计结果,不是词素或词形分析的结果。

没有 BPE 的替代方案都是以序列长度换实现简单:纯字节方案的 ,纯字符方案在非 ASCII 上仍要 1 至 4 字节的编码开销。nanochat 选择字节级 BPE,是因为它在任意输入可编码的前提下把 压到字符级的约三分之一。

原理与推导

1 训练:从字节序列到有序合并表

训练输入是语料与每个片段的出现次数。算法先把每个片段编码为字节序列,再重复 轮「统计、选最大、改写」。

TRAIN-BPE(D, K, pattern):
  chunks ← PRETOKENIZE(D, pattern)          切分为不可跨界的片段
  words[u] ← list(bytes(u))                 每个唯一片段化为字节符号序列
  freq[u]  ← c(u)                           片段出现次数
  V ← {0,...,255}
  M ← []
  repeat k = 1..K:
    stats ← empty map
    for each unique u with freq[u] > 0:
      for i ← 1 to len(words[u]) - 1:
        stats[(words[u][i], words[u][i+1])] += freq[u]
    if stats is empty: break
    (a*, b*) ← ARGMAX(stats)                频次降序,平局按拼接字节串字典序升序
    id ← 256 + (k - 1)
    V.add(id)
    for each unique u: words[u] ← MERGE(words[u], a*, b*, id)
    M.append((a*, b*))
  return M, V

MERGE(w, a, b, id):                         从左到右替换不重叠的相邻对
  out ← []; i ← 1
  while i ≤ len(w):
    if i < len(w) and w[i] == a and w[i+1] == b:
      out.append(id); i ← i + 2
    else:
      out.append(w[i]); i ← i + 1
  return out

朴素实现的复杂度是 ,其中 为语料字节数,每轮都要遍历全部片段。工程实现维护「符号对到出现位置」的倒排索引与优先队列,使每轮代价与该对的实际出现次数成正比,总代价约为 。rustbpe 用 Rust 实现这一优化版本,并把 pattern 作为参数传入,因此 scripts/tok_train.py 才能在默认 2B 字符的语料上以可接受的时间完成训练。

平局处理必须显式固定。若两个符号对频次相同,不同实现可能按字典序、按首次出现位置或按哈希顺序选取,结果是一组同样合法但互不相同的合并表;由于词表 id 依赖合并顺序,两组词表无法逐项比较,只能比较整体压缩率与下游 bpb。本篇与例 2 的代码统一采用「频次降序,其次合并后字节串字典序升序」。

2 推理:按合并序重放

训练得到的合并表是有序规则。编码一个新字符串时,先按同一 pattern 预切分,把每个片段转为字节序列,再按合并序重放规则。tiktoken 把合并表存为 dict[bytes, int] 的 rank 映射,编码等价于反复合并当前序列中 rank 最小的相邻对:

def bpe(mergeable_ranks, piece):
    parts = [bytes([b]) for b in piece]          # 初始为单字节
    while True:
        best_rank, best_pos, best_pair = None, None, None
        for i in range(len(parts) - 1):
            rank = mergeable_ranks.get(parts[i] + parts[i + 1])
            if rank is not None and (best_rank is None or rank < best_rank):
                best_rank, best_pos, best_pair = rank, i, parts[i] + parts[i + 1]
        if best_rank is None:                    # 没有可合并对
            return parts
        parts[best_pos:best_pos + 2] = [best_pair]

该贪心过程与「按 的顺序逐条重写」等价:一条规则一旦在第 轮学到,就不会在后续轮次被重新拆开,因此 rank 更小的对必然对应更早的规则,先处理 rank 最小者不会改变最终结果。例 3 用同一份合并表分别实现两种编码并逐串断言结果相同。

需要强调,编码不是「最优切分」。BPE 不求解任何概率模型下的最大似然切分,只是把训练时学到的规则按顺序应用一遍;同一字符串在不同词表下会得到不同 token 数,这是词表选择的结果,不是编码器实现差异。

3 压缩率与词表规模

设第 次合并在全语料上执行了 次不重叠替换,每次替换把 2 个 token 变成 1 个,因此

例 1 中 ,,,故 ,。该式说明合并的收益完全由 决定:越早的合并出现在高频字节串上, 大;越晚的合并在剩余序列中只匹配少量位置, 小。压缩率 因此是递增但凹的函数。

词表大小的代价由参数与计算两侧构成。若模型维度为 、层数为 ,词表为 :

d24 配置下 、、, 时 ,;若把 提到 100277, 增至 , 升到 1.02。压缩率提高带来的 下降会同时降低注意力与 KV Cache 开销,但词表增大抬高常驻参数与每 token 输出投影,二者的净收益只能由 bpb 或 CORE 判定。

还有一个常被忽略的约束:每个合并产物都要在训练语料中出现足够多次才值得占用一个词表条目。对 32768 的词表,32503 个合并意味着平均每个合并只对应很小的语料频率;这解释了为何扩大词表在固定语料上收益递减,也解释了 --max-chars 默认 2B 与 --doc-cap 10000 的作用:语料覆盖不足时,后段合并会去合并偶然相邻的字节。

4 预切分:SPLIT_PATTERN 的分段语义

nanochat 的 SPLIT_PATTERN 定义在 nanochat/tokenizer.py 第 26 行,共 7 个分支。在任意位置,正则按从左到右的顺序尝试各分支,一旦匹配成功就产出一个片段:

分支匹配内容作用
`'(?i:[sdmt]\ll\ve\re)`英文缩略后缀 's、'd、'm、't、'll、've、're,大小写不敏感让 we're 切成 we 与 're,避免缩略形式被拆成字节
[^\r\n\p{L}\p{N}]?+\p{L}+可选的一个非字母非数字字符加一串字母空格附着到后一个词;汉字属于 \p{L},因此连续汉字成为一个片段
\p{N}{1,2}1 至 2 个数字数字按两位分组,控制数字 token 的数量
?[^\s\p{L}\p{N}]++[\r\n]*可选空格、一串标点符号、尾部换行标点独立成片段,不能与字母合并
\s*[\r\n]到换行为止的空白换行单独处理
\s+(?!\S)后面不再接非空白的空白串行尾或文末的空白
\s+其余空白兜底

两个 Rust 正则语法特性在此处是必需的:?+ 与 ++ 是占有量词(possessive quantifier),匹配后不回退。若换成 Python re 的普通量词,[^\r\n\p{L}\p{N}]?+\p{L}+ 会在失败时回退并放弃前导空格,切分结果随之改变。Python 的 re 模块既不支持 \p{L} 这类 Unicode 属性,也不支持占有量词,直接编译该 pattern 会抛 bad escape \p;Python 的第三方 regex 模块与 tiktoken、rustbpe 使用的 Rust regex 才接受它。

例 4 给出该 pattern 在若干输入上的实测切分。可以直接观察三个后果:空格始终附着在后一个片段上,因此 " world" 与 "world" 是不同的片段;数字被两位一组切开,123456789 变成 5 个片段;标点、换行各自独立,BPE 合并因此无法跨越这些边界。

5 数字切分粒度 \p{N}{1,2} 的取舍

该分支与 GPT-4 的差异只有一处:GPT-4 用 \p{N}{1,3},nanochat 用 \p{N}{1,2}。nanochat/tokenizer.py 的注释说明这是为了避免「在小词表上把过多 token 浪费在数字上」,dev/LOG.md 2026-01-13 条给出验证。

数字串在不同粒度下的片段数如下(每组片段至少占 1 个 token,实际数量取决于该数字串是否已合并为单 token):

数字串{1,1}{1,2}{1,3}
50257532
123456789953
3.14159 的数字部分532

dev/LOG.md 在同一 d12、32K 词表、其余配置不变的条件下报告:

数字粒度val_bpb
\p{N}{1,1}0.969
\p{N}{1,2}0.965
\p{N}{1,3}0.972

结论是 {1,2} 在 32K 词表上最优。机制上可以这样核算:两位分组最多需要 个数字 token,占 32768 的 0.3%;三位分组最多需要 个,占 3.1%,在固定词表预算下会挤占用于字母与汉字的条目;一位分组虽然只需要 10 个数字 token,但长数字的片段数最多,序列变长。{1,2} 在两者之间取得较小的 bpb。该结论与词表大小相关:若词表扩到 100K 以上,三位分组的相对成本下降,最优取值可能变化。

在 nanochat 中的落地

  • nanochat/tokenizer.py 第 23 至 26 行:注释记录 pattern 与 GPT-4 的唯一差异及验证结论,SPLIT_PATTERN 是唯一的预切分定义。
  • 同文件 RustBPETokenizer.train_from_iterator 第 42 至 61 行:先由 rustbpe 用 pattern=SPLIT_PATTERN 训练,再用 tokenizer.get_pattern() 把训练时的 pattern 原样交给 tiktoken.Encoding,从代码路径上消除了训练与推理 pattern 不一致的可能。
  • scripts/tok_train.py:text_iterator() 从 ClimbMix 的 parquet 行组逐批取文档,按 --doc-cap 截断,累计到 --max-chars 停止;随后 RustBPETokenizer.train_from_iterator(text_iter, 32768),训练耗时由 Training time 打印。
  • scripts/tok_eval.py:对 news、korean、code、math、science 与 ClimbMix 的 train/val 文本分别计算 bytes、tokens 与 ratio = bytes / tokens,并与 gpt2、cl100k_base 对比,是判断 pattern 改动影响的主要工具。
  • tests/test_tokenizer.py:断言 decode(encode(text)) == text,覆盖 naïve café 你好 这类混合 Unicode 输入,说明字节级 BPE 对任意 UTF-8 序列可逆。

关键直觉

合并表就是压缩字典

BPE 学到的不是「词」,而是一组按收益排序的字节串替换规则:第 条规则用 1 个词表条目换取 次序列缩短, 是这条收益链的累计结果。严格定义中的 之所以有序,是因为编码必须复现训练的合并顺序;rank 只是把这个顺序编码为整数,使「取最小 rank 的相邻对」与「按 顺序重放」等价。预切分 pattern 则限定了规则可以被应用的范围,因此它和合并表一样是分词器定义的一部分,不能分开存储或分开修改。

例子与代码

例 1:7 次合并的手算全过程

语料由 4 个预切分片段构成,片段已含前导空格(符合 ? 分支的语义),空格记为 ␣:

␣ab   ×4       3 字节/片段
␣abc  ×3       4 字节/片段
␣bd   ×2       3 字节/片段
␣cd   ×2       3 字节/片段

初始符号序列为 ␣ a b、␣ a b c、␣ b d、␣ c d。第一轮统计全部相邻对,共 7 种,总频次 25,等于全部片段的相邻位置数 :

相邻对频次来源
␣a7␣ab 4 + ␣abc 3
ab7␣ab 4 + ␣abc 3
bc3␣abc 3
␣b、bd、␣c、cd2␣bd 2、␣cd 2

最高频两项并列 7。按「频次降序,其次合并后字节串字典序升序」,␣a(字节 20 61)小于 ab(61 62),故第一轮合并 ␣a。逐轮结果如下:

轮次选中合并频次次高改写后的片段
1␣a7ab = 7␣a·b、␣a·b·c、␣·b·d、␣·c·d
2␣a·b7bc = 3␣ab、␣ab·c、␣·b·d、␣·c·d
3␣ab·c3四个并列 2␣ab、␣abc、␣·b·d、␣·c·d
4␣b2bd、␣c、cd 均 2␣ab、␣abc、␣b·d、␣·c·d
5␣b·d2␣c、cd 均 2␣ab、␣abc、␣bd、␣·c·d
6␣c2cd = 2␣ab、␣abc、␣bd、␣c·d
7␣c·d2无␣ab、␣abc、␣bd、␣cd

第 8 轮统计为空,训练停止。合并表为 ,若不计特殊 token,词表大小 。

用该合并表检查 :,,,与「每个片段 1 个 token」一致,。编码未出现的片段 ␣abd 得到 ␣ab | d 两个 token;␣zz 得到 ␣ | z | z 三个 token,说明空格只与训练中见过的字母形成了合并。

例 2:最小可运行的 BPE 训练与编码

以下实现与例 1 的规则逐项对应:片段带频次、按字节为符号、平局按合并后字节串字典序升序、编码按合并序重放。代码约 40 行,可直接运行。

from collections import Counter

chunks = {b" ab": 4, b" abc": 3, b" bd": 2, b" cd": 2}   # 片段与频次
words = [list(k) for k in chunks]                        # 每个片段化为字节符号
freqs = list(chunks.values())
vocab = {i: bytes([i]) for i in range(256)}              # id -> 字节串
merges = []                                              # 有序合并表

for step in range(1, 8):
    stats = Counter()
    for w, f in zip(words, freqs):
        for pair in zip(w, w[1:]):
            stats[pair] += f
    best = sorted(stats.items(), key=lambda kv: (-kv[1], vocab[kv[0][0]] + vocab[kv[0][1]]))[0][0]
    new_id = 256 + len(merges)
    vocab[new_id] = vocab[best[0]] + vocab[best[1]]
    merges.append(best)
    for i, w in enumerate(words):                        # 改写全部片段
        out, j = [], 0
        while j < len(w):
            if j + 1 < len(w) and (w[j], w[j + 1]) == best:
                out.append(new_id); j += 2
            else:
                out.append(w[j]); j += 1
        words[i] = out
    print(f"step {step}: {vocab[new_id]!r} freq {stats[best]} -> id {new_id}")

def encode(s):
    w = list(s.encode())
    for k, (a, b) in enumerate(merges, start=256):       # 按合并序重放
        out, j = [], 0
        while j < len(w):
            if j + 1 < len(w) and w[j] == a and w[j + 1] == b:
                out.append(k); j += 2
            else:
                out.append(w[j]); j += 1
        w = out
    return [vocab[t] for t in w]

for s in [" ab", " abc", " abd", " zz"]:
    print(repr(s), "->", b"|".join(encode(s)), "tokens", len(encode(s)))

运行输出与例 1 的表一致:

step 1: b' a' freq 7 -> id 256
step 2: b' ab' freq 7 -> id 257
step 3: b' abc' freq 3 -> id 258
step 4: b' b' freq 2 -> id 259
step 5: b' bd' freq 2 -> id 260
step 6: b' c' freq 2 -> id 261
step 7: b' cd' freq 2 -> id 262
' ab' -> b' ab' tokens 1
' abc' -> b' abc' tokens 1
' abd' -> b' ab|d' tokens 2
' zz' -> b' |z|z' tokens 3

把 for step in range(1, 8) 改成 range(1, 3),词表只到 257," abc" 会变成 b' ab|c' 两个 token,全部片段的 从 11 升到 22,κ 从 3.27 降到 1.64;这说明合并次数与压缩率的对应关系可以直接在代码中验证。

例 3:rank 贪心编码与顺序重放的等价性

把合并表转成 dict[bytes, int] 的 rank 映射后,可以用 tiktoken 的贪心方式编码,并与例 2 的顺序重放逐串比较:

ranks = {b" a": 256, b" ab": 257, b" abc": 258, b" b": 259, b" bd": 260, b" c": 261, b" cd": 262}

def encode_greedy(s):
    parts = [bytes([b]) for b in s.encode()]
    while True:
        best, best_rank, pos = None, None, None
        for i in range(len(parts) - 1):                  # 找 rank 最小的可合并对
            r = ranks.get(parts[i] + parts[i + 1])
            if r is not None and (best_rank is None or r < best_rank):
                best, best_rank, pos = parts[i] + parts[i + 1], r, i
        if best_rank is None:
            return parts
        parts[pos:pos + 2] = [best]

for s in [" ab", " abc", " abd", " zz"]:
    print(repr(s), encode_greedy(s))
' ab' [b' ab']
' abc' [b' abc']
' abd' [b' ab', b'd']
' zz' [b' ', b'z', b'z']

两种实现的输出逐项相同,原因是 rank 小者必为更早学到的规则,而更早的规则不会在之后被拆开。tiktoken 采用贪心实现是为了在单次扫描中完成编码,便于批处理与多线程;nanochat 的推理路径正是通过 tiktoken.Encoding 走这条实现。

例 4:SPLIT_PATTERN 的实测切分

以下代码用 Python 的 regex 模块执行 pattern(re 模块不支持 \p{L} 与占有量词):

import regex

P = r"""'(?i:[sdmt]|ll|ve|re)|[^\r\n\p{L}\p{N}]?+\p{L}+|\p{N}{1,2}| ?[^\s\p{L}\p{N}]++[\r\n]*|\s*[\r\n]|\s+(?!\S)|\s+"""
for t in ["I'm sure you're right", "123456789", "GPT-2 uses 50257 tokens", "你好世界", "hello, world!"]:
    print(repr(t), "->", regex.findall(P, t))
"I'm sure you're right" -> ['I', "'m", ' sure', ' you', "'re", ' right']
'123456789' -> ['12', '34', '56', '78', '9']
'GPT-2 uses 50257 tokens' -> ['GPT', '-', '2', ' uses', ' ', '50', '25', '7', ' tokens']
'你好世界' -> ['你好世界']
'hello, world!' -> ['hello', ',', ' world', '!']

两点值得注意。GPT-2 中的 2 被单独切出,因为 \p{N}{1,2} 先于标点分支匹配;50257 被切成 50|25|7,第三组只有一位。若把数字分支改成 \p{N}{1,3},50257 会变成 502|57,但词表需要为三位组合支付最多 1000 个条目的预算,这正是第 5 节 bpb 对比所衡量的取舍。

易错点

以下六条在 repo 中都有对应的可检验位置

1. 训练与推理使用不同的 pattern。train_from_iterator 通过 tokenizer.get_pattern() 传递 pattern,若改成硬编码字符串或忘记传参,切分边界变化而 bpb 只会轻微变差,很难定位。

2. 在 Python re 中直接编译 SPLIT_PATTERN。该 pattern 含 \p{L}、\p{N} 与占有量词 ?+、++,re 会抛 bad escape \p;只能用 regex 模块或交给 rustbpe、tiktoken。

3. 把 32768 当作合并次数。合并次数为 ;vocab_size_no_special 包含 256 个字节,断言要求它不小于 256。

4. 认为 BPE 编码给出最优切分。编码只复现训练顺序,不求解最大概率切分;同一字符串在 32K 与 100K 词表下的 token 数差异来自词表,不来自编码器。

5. 忽略空格与片段的绑定。 ? 分支使空格附着到后一个词," world" 与 "world" 是不同片段,因此句首词与句中词的 token 可能不同。

6. 忽略平局规则。频次并列时不同实现的选择不同,词表 id 随之不同;跨实现比较必须比较压缩率与 bpb,不能逐 id 对照。

关联笔记

  • 前置 为什么需要分词:三种粒度的动机与 、、bpb 的换算关系。
  • 后续 词表与特殊token:32768 词表中 256、32503、9 三段的分界与特殊 token 的 id 分配。
  • 后续 nanochat的Rust分词器实现:rustbpe 训练与 tiktoken 推理的代码级分工,以及 token_bytes 的生成。
  • 跨库 Tokenizer与BPE:BPE、WordPiece、Unigram 的通用对比与完整编码算法;本篇只写 nanochat 的 pattern、词表构成与验证数据。
  • 对照 训练数据与FineWeb:词表在 ClimbMix 的 parquet 文档上训练,语料分布与截断策略决定合并表的内容。

达标检测

  • [ ] 写出 BPE 训练伪代码,说明每个符号对的频次为何要按片段出现次数加权。
  • [ ] 对例 1 的语料独立复算第一轮 7 个相邻对的频次与总频次 25,并说明平局规则如何决定第一轮选择。
  • [ ] 用 核算例 1 的 36 字节到 11 个 token,指出每一步的 。
  • [ ] 解释 rank 贪心编码与合并序重放为何等价,并给出一个二者会分歧的假设情形及该情形不成立的理由。
  • [ ] 逐段解释 SPLIT_PATTERN 的 7 个分支,并预测 50257、we're、你好世界、a\nb 的片段划分。
  • [ ] 说明 \p{N}{1,2} 与 \p{N}{1,3} 在 32K 词表下的成本差异,并复述 dev/LOG.md 的三组 val_bpb。
  • [ ] 修改例 2 的合并轮数为 3 与 7,记录词表大小、κ 与 " abc" 的 token 数变化。

参考来源

  • Sennrich et al., "Neural Machine Translation of Rare Words with Subword Units", arXiv:1508.07909 —— 对应本篇第 1 节的 BPE 训练算法与合并表定义。
  • Radford et al., "Language Models are Unsupervised Multitask Learners", 2019 —— 对应字节级 BPE 的基础符号集与 GPT-2 词表构成。
  • OpenAI, tiktoken 仓库(tiktoken_ext/openai_public.py 与 README 中 GPT-4 分词器说明)—— 对应第 2 节的 rank 贪心合并与 cl100k_base 的 \p{N}{1,3}。
  • Karpathy, rustbpe 仓库 —— 对应第 1 节的 Rust 训练实现、get_pattern 与 get_mergeable_ranks 接口。
  • Karpathy, nanochat 仓库(commit 92d63d4):nanochat/tokenizer.py、dev/LOG.md 2026-01-13「Number Token Split Pattern」条 —— 对应 SPLIT_PATTERN 的逐分支解释与数字粒度的 bpb 实验。