byte-level 编码器 (2)

阶段: B1 · evals 方法论 + tokenization 起步（Day 1-10） 标签: #tokenization #bpe #merge-training #vocab-growth

今日导引（由浅入深）

Day 7 写完了编码器骨架（vocab/merge 表/encode/decode），但留了一个洞：merge 表是从哪来的？

今天补上——精读 BPE 的训练算法：统计全语料相邻 pair 频次 → 贪心合并最高频 pair → 更新序列 → 重复，直到达 vocab 上限或频次阈值。

这是 B1 tokenization 支线的「核心算法日」：Day 3 手算过单 prompt 的前 3 次 merge，今天把同样的逻辑跑到 29 个 eval prompt 的全语料上，看 vocab 随 merge 数怎么增长。

最小可判定产出：在 29 prompt 上跑通 trainBpe，实测 vocab=456（256 base + 200 merges），测试绿。

明天 Day 9 用训好的表出全量 token 报告，Day 10 与计费对齐收口。

1. 机理精读

merge 训练 = 统计 → 贪心合并 → 更新 → 重复 → 停止，五段循环。 逐段拆：

① 统计（count adjacent pairs）。

扫全语料的每个序列，统计每个相邻 pair (a,b) 出现多少次。第一轮全是字节级 pair（如英文里 (t,h)、(i,n) 高频）。

这是贪心的「目标函数」原料——频次高的 pair 合并后压缩收益最大。

② 贪心合并最高频 pair。

取频次最高的 pair，分配一个新 id（本仓是 256 + i，i 为当前 merge 序号 = rank），写进 merge 表。

「贪心」意味着只看当下最高频、不回头优化全局——这是 BPE 与「最优分词」的本质区别：BPE 不求最优编码，只求一个确定、可复现、压缩还不错的分词。

③ 更新序列。

把全语料里所有该 pair 替换成新 id（本仓 mergePair）。

每次 merge 让 vocab+1、序列变短（至少不变长）——这正是「压缩」的来源：高频子串被压成单 token，后续轮次又可能基于这个新 token 合并出更长的子串（如 (th, e) → the）。

④ 重复。

回到 ①，在更新后的序列上重新统计。注意频次必须每轮重算——因为上一轮的合并改变了相邻关系。

⑤ 停止条件。

两种：达到 numMerges 上限（本仓 200），或频次阈值（没有任何 pair 重复出现≥2 次时提前停）。

本仓 trainBpe 里 if (bestC < 2) break——一个只出现一次的 pair 合并它没有压缩意义，是「无 pair 可合」的自然终点。

为什么 vocab 增长是线性的？

每轮恰好 +1 个新 id（256→257→…）。在本仓 29 prompt 小语料上跑 200 merges，vocab 从 256 线性涨到 456（256 base + 200 merges）。size 字段就是 256 + merges.size。

关键权衡 / 边界：小语料下 200 merges 只是教学量级。

生产 vocab 通常 ≥32k（GPT-4 的 cl100k ~100k），更大 vocab → 更短序列 → 更省 token，但也更大 embedding 表、更稀疏的低频 token。

绝不能用这个小词表的压缩率外推生产模型的计费（Day 9 的 c/t 比同理）。

与相邻概念的边界：训练算法（今天）产出 merge 表；encode（Day 7）消费 merge 表；两者用同一个 mergePair 底层操作，但训练是「学顺序」、encode 是「按顺序应用」。

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

代码日。Read src/agent/eval/tokenizer.ts 的 trainBpe，真实走读五段循环：

• 签名：trainBpe(corpus: string[], numMerges: number): BpeModel。docs = corpus.map(toBytes)——先把每个文档转字节数组。
• 统计（每轮）：const counts = new Map<string, number>()，双层循环扫所有 docs 的相邻 pair，counts.set(k, (counts.get(k) ?? 0) + 1)。对应机理 ①。
• 选最高频 + 决定论 tie-break：if (c > bestC || (c === bestC && bestK !== '' && k < bestK))——频次相同时取字典序更小的 pair key，注释写「Ties broken by smallest pair key for determinism」。这条保证同语料同 numMerges 两次训练结果完全一致（Day 7 那条决定论测试就靠它）。对应机理 ②。
• 停止条件：if (bestC < 2) break——最高频 pair 也只出现 1 次就停，对应机理 ⑤「无重复 pair 可合」。
• 登记 merge：const newId = 256 + i; merges.set(bestK, i); expand.set(newId, [a, b])——正向表存 rank、反向表存展开，rank = merge 序号 i。
• 更新全语料：for (let d = 0; d < docs.length; d++) docs[d] = mergePair(docs[d]!, a, b, newId)，对应机理 ③。
• 返回：{ merges, expand, size: 256 + merges.size }。

手算 vocab 增长（验证线性）：

• 第 0 轮 merge → 新 id 256，vocab=257；
• 第 1 轮 → id 257，vocab=258；
• …；
• 第 199 轮 → id 455，vocab=456。

即 vocab(k) = 256 + k，k=merge 数。29 prompt 跑满 200 merges（语料够大，未触发 bestC < 2 提前停），落到实测 vocab=456。

一个最小训练手算例（语料 = ["aaab", "aab"] 的字节流，看前 2 merge）：

• 第 0 轮统计：pair (a,a) 出现 aaab 里 2 次 + aab 里 1 次 = 3 次；(a,b) 出现 2 次。最高频 (a,a)=3 → 合并成 id 256。序列变 [256,a,b]、[256,b]。
• 第 1 轮统计：(256,a) 1 次、(a,b) 1 次、(256,b) 1 次——三者并列 1 次。bestC < 2？这里 bestC=1 < 2 → 停（若 numMerges 仍大于 1 也会因频次阈值早停）。
• 结论：小语料很快触发 bestC < 2 早停；29 prompt 语料够大才能跑满 200 merges 到 vocab=456。

测试走读（tokenizer.test.ts）：

• const model = trainBpe(corpus, 200)（corpus = 29 个 EVAL_TASKS prompt）；
• expect(model.size).toBeGreaterThan(256) 与 model.merges.size > 0 验证训练真的产出了 merge；
• 决定论用例 trainBpe(corpus, 100) 两次 totalTokens 相等。

3. 今日实战

照 seed：用 trainBpe（tokenizer.ts）在 29 个 eval prompt 上训练 merge 表，记 vocab 增长曲线（merge 数 vs vocab-size）。

1. corpus = EVAL_TASKS.map(t => t.prompt)（29 条）。
2. 对 numMerges ∈ {0, 50, 100, 150, 200} 各跑一次 trainBpe，记录 model.size，画 merge 数 → vocab-size 曲线（应为线性 256 + k）。
3. 用 numMerges=200 的模型确认 model.size === 456，进 vitest 全量绿。

4. 今日实测 / 产出

• 已完成——实测 vocab=456（256 base + 200 merges），训练在 29 prompt 上跑通，测试绿。
• vocab 增长曲线由 200 merges 线性递增（256→456）。
• 状态：已完成（非待跑/待建）；token 计量报告留 Day 9，与计费对齐留 Day 10。

5. 常见误区 / 陷阱

• 频次不每轮重算：合并改变了相邻关系，沿用旧 counts 会选错下一个 pair。本仓每轮新建 counts。
• tie-break 不确定：频次相同不定序，会破坏决定论 → 测试间歇失败。本仓用最小 pair key 兜底。
• 用 200-merge 小词表外推生产压缩率：小语料 vocab 太小，c/t 比和压缩率都不可外推到 ≥32k 的生产 vocab。
• 忘了停止条件：没有 bestC < 2 早停，小语料上后期会把只出现一次的 pair 也合并，浪费 vocab 且无压缩收益。

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

• Karpathy minbpe / 《Let's build the GPT Tokenizer》(Zero-to-Hero, 2024) — 贪心 merge 训练的参考实现，本仓 trainBpe 同源。
• Sennrich et al.《Neural Machine Translation of Rare Words with Subword Units》(BPE 原始论文, 2016-06) — 统计-合并-停止的算法出处。
• Sebastian Raschka《Build a LLM (From Scratch)》(2024-09) — vocab 大小与序列长度的权衡。
• 本仓 src/agent/eval/tokenizer.ts trainBpe（2026-06，repo 内）— 五段循环 + 决定论 tie-break + bestC<2 早停。

SOTA检查 (2026-06 更新)

• 当前主流：贪心 BPE merge 仍是标准训练算法（tiktoken / HF tokenizers 同源），仍 SOTA，有效。
• 过时黑名单：小语料下 200 merges 仅作教学；生产 vocab 通常 ≥32k，避免直接外推此小词表的压缩率/c-t 结论到生产模型。
• 下次复查点：是否出现替代 BPE 的训练范式（如 unigram LM tokenizer、byte-latent/tokenizer-free）成为新生产主流；目前贪心 BPE 仍是 2026 主线。

衔接

• 昨天：Day 7 — byte-level 编码器 (1)（vocab/merge 表/encode 骨架，5 prompt roundtrip 绿）。
• 今天：精读 merge 训练算法，在 29 prompt 上训出 vocab=456，线性增长曲线，测试绿。
• 明天：Day 9 — 全量编码 + token 报告，用训好的表对 29 prompt 出 tokenReport，实测 totalTokens=1760、≈2.01 c/t。