BPE/tokenization 原理

阶段: B1 · evals 方法论 + tokenization 起步（Day 1-10） 标签: #tokenization #bpe #byte-level #minbpe

今日导引（由浅入深）

前两天（Day 1/2）立的是 eval 方法论：怎么判、谁来判。今天转入 B1 的第二条主线——tokenization，回答一个看似无关其实极现实的问题：调用模型要花多少钱。OpenRouter 按 token 计价，而 token 不是字符也不是单词，是 BPE 切出来的子串。要在发请求前预估成本，就得先理解 token 怎么来的。今天只学原理 + 手算，为 Day 7-9 自写 byte-level BPE tokenizer、Day 10 双数对齐打底。最小可判定产出：取 1 个真实 eval prompt，手算它前 3 次 BPE merge 的完整 transcript。

1. 机理精读

BPE（Byte-Pair Encoding）从 byte-level 起步。基础词表是 256 个字节（0x00–0xFF）。任何文本先 UTF-8 编码成字节序列，于是初始 token 就是这 256 个字节 id。然后反复做一件事：统计当前序列里最高频的相邻 pair，把它 merge 成一个新 token（新 id = 256 + 该 merge 的序号），直到达到目标 vocab 大小或没有可合并的高频 pair。

为什么不按字符切、不按单词切。Karpathy《Zero-to-Hero》(minbpe 系列) + Raschka (2024-09) 给的理由：

• byte-level 无 OOV（out-of-vocabulary）：任何字符串都能被 256 个字节表示，永远不会遇到「词表里没有这个词」的死角。纯 word-level tokenizer 会被新词、拼写错误、罕见专名打穿。
• 天然多语言 / 多模态友好：字节是语言无关的，中文、emoji、代码、JSON 全都落在同一套字节空间，不需要为每种语言单独建词表。
• merge 让常见子串压缩成单 token：高频子串（如 tion、the、0x）被合并后，一个 token 顶原来好几个字节，序列变短 → 上下文窗口装得下更多内容、计费 token 数下降。这正是 tokenization 与成本挂钩的机理。

关键权衡。merge 数（即词表大小）是一个旋钮：merge 越多，词表越大，常见子串压得越狠、序列越短（c/t 比越高），但词表本身越大、低频 token 越多。生产词表通常 ≥32k；教学小语料用几百个 merge 即可看清机理。压缩率（chars per token）强依赖语料：英文 + JSON 偏低，纯中文或代码会不同——这条到 Day 9 会用实测数字（≈2.01 c/t）坐实。

训练 vs 编码是两个不同算法。这点初学最易混：

• 训练（train）：输入全语料，统计相邻 pair 频次 → 贪心合并最高频 pair → 更新序列 → 重复，产出一张 merge 表（pair → rank）。它是「学一套切分规则」。
• 编码（encode）：输入单条文本 + 已训好的 merge 表，反复应用 rank 最低（最早学到）的可用 merge，直到没有可用 merge。它是「用学好的规则切一条文本」。GPT-2 风格 encode 严格按 merge rank 顺序应用，保证训练与推理切分一致。

decode 是 encode 的无损逆。每个 ≥256 的 token id 都记录了它展开成哪两个子 id（expand 表），递归展开到字节再 UTF-8 解码，必然还原原文——这是「byte-level 无 OOV」的另一面：任何 token 都能无损还原成字节。Round-trip decode(encode(x)) === x 是 Day 7 的核心单测。

与相邻概念的边界。今天是「BPE 怎么训、怎么把文本切成 token」的原理；Day 7-8 是把它写成代码（trainBpe/encode/decode）；Day 9 是用它产出 token 报告（→ 成本，实测 1760 token / ≈2.01 c/t）；Day 4-5 是真把请求发出去看 OpenRouter 实际计费。今天的手算是后面所有代码的「心智参考实现」——Day 7 代码里 trainBpe 的贪心循环、tie-break、停止条件（bestC < 2 break），全是今天手算逻辑的直译。

2. 推导 / 手算 / 代码走读

今天是手算日。取一个短真实 eval prompt 片段，逐步走前 3 次 merge。以 tasks.ts 里 aml-ctr-threshold 的核心短语为例，取一段足够小的字符串便于手算（实际产出按所选完整 prompt 实算）。

设手算样本为字符串 "aaba aaba"（一个最小可控例子，演示算法本身；真实产出用真 prompt 的 UTF-8 字节）：

第 0 步：byte 序列。UTF-8 下 ASCII 字符 = 自身码点： a=97, b=98, space=32。 序列 = [97,97,98,32,97,97,98]（注意此处用单空格示意，真实 prompt 按其字节）。

统计相邻 pair 频次：

• (97,97) 出现 2 次（位置 0-1、4-5）
• (97,98) 出现 2 次（位置 1-2、5-6）
• (98,32) 1 次
• (32,97) 1 次

第 1 次 merge：最高频是 (97,97) 与 (97,98) 都为 2 → 平局，按确定性规则（最小 pair key）选 (97,97)（"97,97" < "97,98"）。新 id = 256。 合并后序列 = [256,98,32,256,98]（每个 97 97 → 256）。记录 merge: (97,97)→256。

第 2 次 merge：新序列相邻 pair：(256,98) ×2、(98,32) ×1、(32,256) ×1。最高频 (256,98)=2 → 新 id=257。 合并后 = [257,32,257]。记录 merge: (256,98)→257。

第 3 次 merge：相邻 pair：(257,32) ×1、(32,257) ×1，都只有 1 次 < 2 → 停止条件触发（没有重复 pair 值得 merge）。手算到此 3 步（第 3 步为「无 merge 可做」的终止）。

逐步记录表：

要点：每次 merge vocab+1、序列变短；平局用确定性 tie-break（最小 key）保证可复现——这正是 Day 7 代码 trainBpe 里 c === bestC && k < bestK 的逻辑。真实产出用一条完整 eval prompt 的 UTF-8 字节实算，含 merge 后 token 数。

用这条手算预读代码。把上面的手算和 src/agent/eval/tokenizer.ts 的 trainBpe 对照（Day 7 会细走读，这里先建立映射）：

• 「统计相邻 pair 频次」= trainBpe 内层双循环填 counts: Map<string,number>，key 用 a+','+b。
• 「选最高频 + tie-break 最小 key」= if (c > bestC || (c === bestC && bestK !== '' && k < bestK))。
• 「没有重复 pair 就停」= if (bestC < 2) break。
• 「合并后序列」= mergePair(seq, a, b, newId)，新 newId = 256 + i（i 是 merge 序号）。
• 「记录展开关系供 decode」= expand.set(newId, [a, b])。

所以今天手算不是练习题，是把生产代码的每一行翻成纸面动作——明白这点，Day 7 读代码会非常快。

3. 今日实战

1. 从 src/agent/eval/tasks.ts 取 1 条 eval prompt（建议短的，如 aml-ctr-threshold 或 aml-sar-deadline）。
2. 写出它的完整 UTF-8 byte 序列。
3. 统计相邻 pair 频次，手算前 3 次 merge：每步记「合并了哪个 pair / 生成哪个新 id / 合并后 token 数」。
4. 把 transcript 落到本日笔记产物（与 day3 配套），不写代码——代码是 Day 7-8 的事，今天纯手算验证心智模型。

4. 今日实测 / 产出

• 产出：单 prompt 的 BPE merge 手算 transcript（含 merge 后 token 数）。
• 状态：手算产物，按所选 prompt 实算。
• 不臆造数字；手算结果取决于所选 prompt 的真实字节分布。

4b. 为什么自写 tokenizer 而不是直接调库

生产当然用 tiktoken / HF tokenizers，但本仓自写一个 byte-level BPE 有三个不可替代的理由：(1) 零依赖、零 key 就能在发任何请求前估算 token → 成本，这对「无 key 也要有数」的纪律至关重要；(2) 自写过一遍，才真的理解 c/t 比为何随语料变、为何 output token 不可预估——这是 Day 4/10 成本分析的认知前提；(3) 它是确定性纯函数，可单测可复现，符合「核心数学必须可测」的范式（与 Day 5 的 κ/聚合同源）。所以自写不是重复造轮子，是把「token→成本」这条链的每一环都变成自己能掌控、能测试、能解释的代码。代价是：自写小词表的切分不等于模型官方 tokenizer 的切分，所以它只能做量级估算，不能当计费真相——这条边界 Day 9/10 会反复强调。

5. 常见误区 / 陷阱

• 以为 BPE 按字符或单词切：错。它从 256 字节起步、靠数据驱动 merge——这也是为什么没有 OOV。
• 忽略 tie-break 的确定性：平局不规定怎么选，merge 表就不可复现；本仓用「最小 pair key」打破平局。
• 把小语料的 c/t 比外推到生产：几百个 merge 的小词表压缩率不能等同 32k+ 生产词表（Day 8/9 会再警示）。
• 混淆「训练 merge」与「encode」：训练是统计全语料贪心合并产出 merge 表；encode 是对单条文本反复应用「最低 rank 的可用 merge」（GPT-2 风格，Day 7 代码体现）。

4c. 压缩率（c/t）的直觉

Day 9 会实测 meanCharsPerToken ≈ 2.01（英文 + JSON 语料、小词表 200 merges）。怎么读这个数？它表示「平均每个 token 顶约 2 个字符」。对照感受：

• 纯英文自然语言、大词表（如 GPT 系生产 tokenizer）c/t 常在 4 左右（一个 token 顶约 4 字符）。
• 本仓 ≈2.01 偏低，因为：(a) 词表小（仅 200 merges），高频子串没被充分合并；(b) 语料含大量 JSON 标点 / 地址 / 数字，可压缩冗余少。
• 中文每字常占 3 字节（UTF-8），byte-level 下 c/t 表现又不同。

关键认知：c/t 强依赖语料 + 词表大小，不能把小词表的 2.01 外推到生产。它只用来给「这批 prompt 大概多少 token」一个量级，真实计费仍以模型官方 tokenizer 为准。

6. 学习资源（每条带 YYYY-MM）

• Andrej Karpathy, Zero-to-Hero / minbpe（2024，教学黄金路径）—— byte-level BPE 参考实现心智。
• Sebastian Raschka, Build a Tokenizer / BPE 讲解（2024-09）—— 为何 byte-level、merge 机理。
• 生产参考：OpenAI tiktoken 与 HuggingFace tokenizers（byte-level BPE，持续维护）—— 当前生产 SOTA。
• 仓库代码（Day 7-9 走读对象）：src/agent/eval/tokenizer.ts（trainBpe/encode/decode/tokenReport）。

SOTA检查 (2026-06 更新)

• 当前主流：Karpathy minbpe + Raschka 2024-09 仍是教学黄金路径，BPE 原理稳定不过时。
• 生产 SOTA：tiktoken / HF tokenizers 的 byte-level BPE 仍是主流（2026）。
• 过时黑名单：避免引用过时的 word-level 或纯字符 tokenizer 叙事（有 OOV、多语言差）；自写小词表 tokenizer 仅供成本测算/原理验证，不可当生产 tokenizer。
• 下次复查：关注是否有 byte-level 之外的新分词范式（如 token-free / byte-latent transformer）成为主线；若成主流，更新「byte-level BPE 仍 SOTA」结论。

衔接

• 昨天：Day 2 — 三种 grader（code/LLM-judge/human）+ self-preference 循环自评。
• 今天：BPE 从 256 字节起步、贪心 merge 高频 pair 压缩序列；手算前 3 次 merge。
• 明天：Day 4 — OpenRouter 接入（把 token 换算成真实 input/output 计价与上下文窗口）。