byte-level 编码器 (1)

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

今日导引（由浅入深）

B1→B18 能力曲线上，Day 1-6 是「评测方法论」这条支线，Day 7-10 切到「tokenization 工程」这条支线——但两条线在 B1 末尾会合。

自写 tokenizer 的最终用途是：在不花一分钱、不调任何 API 的前提下，估算 eval prompt 的 token 量 → 进而估算 OpenRouter 成本。

Day 3 已经手算过 BPE 的前 3 次 merge（纸面原理），今天把原理落成可运行、可测试的代码骨架 tokenizer.ts：vocab 初始化、merge 表数据结构、encode 主循环。

最小可判定产出：5 个短 prompt 跑通 encode + decode roundtrip 通过，测试绿。

明天 Day 8 训练 merge 表、Day 9 出全量 token 报告、Day 10 与计费对齐收口——所以今天是 tokenization 支线的「数据结构奠基日」。

1. 机理精读

byte-level BPE 编码器是三件套：vocab 初始化 + merge 表 + encode 主循环。 今天复盘并落码这三件，理解它们各自「为什么这样设计」。

① vocab 初始化（256 byte → id）。

一切从 256 个基础字节开始（id 0-255 就是字节本身）。这是 byte-level 的核心选择：不按字符切、按 UTF-8 字节切。

代价是一个汉字会被拆成 3 个字节（多个起始 token）；收益是永远没有 OOV（out-of-vocabulary）——任何 Unicode 串都能被 256 个字节表示，天然多语言、天然处理 emoji/代码/乱码。

本仓 tokenizer.ts 用 TextEncoder / TextDecoder 做字符串↔字节，所以 roundtrip 对非 ASCII（如 'structuring 结构化 $9,800'）也无损。

② merge 表数据结构（pair → 新 id 的有序表）。

这是 BPE 的核心数据结构。本仓用 merges: Map<string, number>，key 是 "a,b"（两个 id 拼成的字符串），value 是 rank（0-based 合并顺序）；合并出的新 token id = 256 + rank。

为什么要有序（rank 而非布尔）？因为 encode 时必须按训练时的合并顺序应用 merge——先合并的优先级高。

另配一个 expand: Map<number, [number,number]> 记录每个新 id 展开成哪两个 id，供 decode 反向还原。这一对（merges 正向、expand 反向）保证编码可逆。

③ encode 主循环（反复扫描，应用最早可用的 merge）。

给定一段文本的字节序列，反复扫描相邻 pair，找 rank 最小（最早训练出）的可应用 merge，合并它，再扫，直到没有任何 pair 在 merge 表里。

这是 GPT-2 风格的贪心 encode——不保证全局最优分词，但确定、快、与训练顺序一致。

关键权衡：encode 每轮 O(n) 扫描、最多 merge n 次，朴素实现是 O(n²)；生产库（tiktoken）用更聪明的优先队列 / 正则预切，但教学版用朴素循环最清晰。

与相邻概念的边界：今天只写 vocab + merge 表结构 + encode/decode 骨架，merge 训练（怎么从语料学出 merge 表）留到 Day 8。

也就是说今天的测试可以先用一个小 corpus 训出表、验证 encode/decode 可逆，但「训练算法的统计-贪心-停止」三段在 Day 8 才精读。

参考实现心智是 Karpathy 的 minbpe，与 tiktoken 同源。

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

今天是代码日。Read src/agent/eval/tokenizer.ts（4.4KB，零依赖），真实符号走读：

• BpeModel（interface）：merges: Map<string, number>（"a,b"→rank）、expand: Map<number,[number,number]>（新 id→展开对，供 decode）、size: number（= 256 + merges.size）。
• 文件头注释：直说「the mechanism is the code, the number is the report」——这是「implemented, not noted」的执行体现。
• toBytes(s) / key(a,b)：toBytes 用 new TextEncoder().encode(s) 转字节数组；key 把两个 id 拼成 a + ',' + b 作 Map key。
• mergePair(seq, a, b, newId)：扫一遍序列，把相邻的 (a,b) 替换成 newId，i++ 跳过已合并的右半。这是训练和 encode 共用的底层操作。
• trainBpe(corpus, numMerges)（今天只写骨架，算法 Day 8 精读）：返回 BpeModel，size: 256 + merges.size。
• encode(text, model)：主循环——while (seq.length >= 2) 找 model.merges.get(key(...)) 中 rank 最小（r < bestRank）的 pair，合并成 256 + bestRank；bestRank === Infinity（无可用 merge）时 break。GPT-2 style，逐字对应上文「应用最早可用 merge」。
• decode(ids, model)：递归 emit——id < 256 直接 push 字节，否则查 expand 展开成左右两半再递归 emit，最后 TextDecoder().decode。这是 encode 的无损逆。

roundtrip 单测走读（src/agent/__tests__/eval/tokenizer.test.ts，真实在 repo）：

• corpus = EVAL_TASKS.map(t => t.prompt)（29 个 eval prompt），model = trainBpe(corpus, 200)。
• 'round-trips losslessly'：对 corpus.slice(0,5) + 'structuring 结构化 $9,800' + ''（空串），断言 decode(encode(s, model), model) === s。正是 seed 说的「5 个短 prompt 跑通 encode + roundtrip 通过」。
• 'trains merges and grows the vocab'：model.size > 256 且 model.merges.size > 0。
• 'is deterministic'：同 corpus + numMerges 两次训练，totalTokens 相等（决定论由 trainBpe 里「ties broken by smallest pair key」保证）。

一个最小手算例（验证 encode 贪心）：

设语料训出 merge 表 {(t,h):0, (th,e):1}（rank 0 先于 rank 1）。

编码 "the" 的字节序列 [t,h,e]：

1. 扫描相邻 pair：(t,h) rank=0、(h,e) 不在表。取最小 rank=0 → 合并 (t,h) 成 id 256，序列变 [256,e]。
2. 再扫：(256,e) = (th,e) rank=1 → 合并成 id 257，序列变 [257]。
3. 无可用 merge → 停。"the" 编成单 token [257]，3 字符压成 1 token。

decode [257]：展开 257→(256,e)→(t,h),e→字节 t,h,e → "the"，无损还原。

为什么 encode 必须选「最小 rank」而非「任意可合」？

• merge 表是有训练顺序的：rank 0 的 (t,h) 是训练时最先合并出来的高频 pair。
• 若 encode 时先合 rank 1 的 (h,e)（假设它也在表里），序列会变成 [t,he]，而 [t,he] 这个组合训练时从未出现过 → 后续可能再也合不动 → 切分与训练分布不一致。
• 按最小 rank 贪心，等价于「沿着训练时的合并轨迹回放」，保证 encode 的切分落在 decode 能还原的轨道上。

roundtrip 为什么对空串和非 ASCII 也成立？

• 空串 '' → toBytes 得 [] → encode 的 while (seq.length >= 2) 直接不进循环 → 返回 [] → decode([]) 得 ''。边界自然闭合。
• '结构化' → TextEncoder 切成 9 个 UTF-8 字节（每汉字 3 字节）→ 这些字节 id 全在 0-255 base 里 → 即使没被任何 merge 命中，也能逐字节 TextDecoder 还原。byte-level 的 no-OOV 在这里体现为 roundtrip 永远无损。

3. 今日实战

照 seed：在 src/agent/eval/tokenizer.ts 写 byte→id 与 merge 表骨架（trainBpe / encode / decode），对 5 个短 prompt 跑通 encode，测试落 src/agent/__tests__/eval/tokenizer.test.ts。

1. 实现 BpeModel 结构（merges 正向 + expand 反向 + size）。
2. 实现 encode（贪心找最小 rank pair）与 decode（递归展开），保证 roundtrip 无损（含非 ASCII 与空串）。
3. 写 vitest：decode(encode(s, model), model) === s、model.size > 256、决定论断言。
4. pnpm test 让 tokenizer.test.ts 进全量绿。

4. 今日实测 / 产出

• 已完成——tokenizer 测试绿（tokenizer.test.ts 在全量 378 passing 内），encode/decode roundtrip 通过（含 'structuring 结构化 $9,800' 与空串两个边界）。
• 产出文件：src/agent/eval/tokenizer.ts（trainBpe/encode/decode/tokenReport，零依赖）+ src/agent/__tests__/eval/tokenizer.test.ts（4 个用例）。
• 状态：已完成（非待跑/待建）；今天只验 encode/decode 骨架，merge 训练曲线留 Day 8、token 报告留 Day 9。

5. 常见误区 / 陷阱

• 把 byte-level 当 char-level：一个汉字 = 3 个字节 = 多个起始 token，别按字符数估 token 数。
• merge 表用布尔而非 rank：必须记录合并顺序（rank），否则 encode 时无法「先合并先训练出的」，分词会错。
• encode 不按最小 rank 贪心：随便选一个可合并 pair 会与训练顺序不一致，破坏与 decode 的可逆性。
• decode 漏掉递归展开：新 id（≥256）必须递归展开成字节才能 TextDecoder，直接当字节会乱码。

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

• Karpathy《Let's build the GPT Tokenizer》/ minbpe (Zero-to-Hero, 2024) — 自写 byte-level BPE 的参考实现心智。
• Sebastian Raschka《Build a Large Language Model (From Scratch)》tokenization 章 (2024-09) — byte-level vs char/word 的取舍。
• OpenAI tiktoken 文档（byte-level BPE，2024 起持续维护）— 生产侧同源实现，自写仅作量级估算对照。
• 本仓 src/agent/eval/tokenizer.ts + tokenizer.test.ts（2026-06，repo 内）— 真实 trainBpe/encode/decode/tokenReport。

SOTA检查 (2026-06 更新)

• 当前主流：自写 byte-level BPE 教学价值稳定，与 tiktoken 思路同源，仍是教学黄金路径，原理不过时。
• 生产 SOTA：tiktoken / HF tokenizers 的 byte-level BPE。自写仅供成本测算与原理验证，不可当生产 tokenizer。
• 过时黑名单：避免引用过时的 word-level 或纯字符 tokenizer 叙事（有 OOV、不多语言）。
• 下次复查点：是否出现 tokenizer-free / byte-latent（如 byte-level Transformer、BLT 类）新范式动摇 BPE 主流地位；目前 BPE 仍是 2026 生产标准。

衔接

• 昨天：Day 6 — 解析首跑结果（失败归因到 6 类 taxonomy，top-3 占比）。
• 今天：把 Day 3 的 BPE 原理落成可运行代码——vocab/merge 表/encode 主循环，5 prompt roundtrip 测试绿。
• 明天：Day 8 — byte-level 编码器 (2)，精读 merge 训练算法（统计 pair → 贪心合并 → 停止条件），在 29 prompt 上训出 vocab 增长曲线。