Appearance
Part 2: 分词与采样
BPE tokenizer、采样策略、softmax
1. BPE 分词器
模型只能处理数字。分词器是文本和数字之间的桥梁——"你好"变成 [3472, 19238] 才能进入模型。今天学习哈希表、BPE 合并算法，以及 Chat 模板如何组装最终输入。
C 知识点
1. 开放寻址哈希表（Open Addressing Hash Table）
ds4.c 实现了一个简单的开放寻址哈希表，用于 token 字符串到 ID 的映射：
c
typedef struct {
ds4_str key; // 键（字符串视图，指向 mmap）
int value; // 值（token ID）
bool used; // 该槽位是否被占用
} str_i32_entry;
typedef struct {
str_i32_entry *entry; // 槽位数组
uint64_t cap; // 容量（2 的幂次）
uint64_t used; // 已使用数
} str_i32_table;插入操作（table_put）：
c
static void table_put(str_i32_table *t, ds4_str key, int value) {
uint64_t mask = t->cap - 1; // 容量必须是 2 的幂
uint64_t i = hash_bytes(key.ptr, key.len) & mask; // 计算起始位置
while (t->entry[i].used) { // 线性探测
if (ds4_str_eq(t->entry[i].key, key)) { // 已存在→更新
t->entry[i].value = value;
return;
}
i = (i + 1) & mask; // 环形前进
}
t->entry[i].used = true; // 找到空位→插入
t->entry[i].key = key;
t->entry[i].value = value;
t->used++;
}关键点：
- 容量必须是 2 的幂：这样
mask = cap - 1可以用位与& mask代替取模% cap，更快 - 线性探测：冲突时检查下一个位置
i = (i+1) & mask - 环形：到达末尾后回到开头
- 不扩容：初始化时预分配
2 * expected + 16的空间，保证负载因子 < 50%
2. FNV-1a 哈希函数
c
static uint64_t hash_bytes(const void *ptr, uint64_t len) {
const uint8_t *p = ptr;
uint64_t h = 1469598103934665603ull; // FNV offset basis
for (uint64_t i = 0; i < len; i++) {
h ^= p[i]; // XOR 当前字节
h *= 1099511628211ull; // 乘以 FNV prime
}
return h;
}FNV-1a 简单、快速、分布均匀。对于 token 字符串查找足够好。
3. 动态数组（Dynamic Array）
c
typedef struct {
int *v;
int len;
int cap;
} ds4_tokens;
static void token_vec_push(token_vec *tv, int token) {
if (tv->len == tv->cap) { // 容量不够
tv->cap = tv->cap ? tv->cap * 2 : 64; // 翻倍（首次用 64）
tv->v = xrealloc(tv->v, (size_t)tv->cap * sizeof(tv->v[0]));
}
tv->v[tv->len++] = token; // 追加元素
}这是 C 语言中最常见的"可增长数组"模式：
len：当前元素数cap：分配的容量- 增长策略：翻倍（amortized O(1) 插入）
4. UTF-8 字符串操作
ds4.c 包含 UTF-8 辅助函数：
c
// 从首字节判断 UTF-8 字符长度
static int utf8_len_from_first_byte(uint8_t c) {
if (c < 0x80) return 1; // ASCII: 1 字节
if ((c & 0xE0) == 0xC0) return 2; // 110xxxxx: 2 字节
if ((c & 0xF0) == 0xE0) return 3; // 1110xxxx: 3 字节
if ((c & 0xF8) == 0xF0) return 4; // 11110xxx: 4 字节
return 1; // 无效字节，当作 1 字节
}UTF-8 编码中首字节的前导 1 的数量指示了该字符的字节数。这个技巧在处理多语言文本时很常用。
LLM 知识点
1. 什么是 Token
LLM 不直接处理字符，而是处理 token——文本的子词单元：
"Hello world" → [15496, 995] （2 个 token）
"Hello 世界" → [15496, 995, 105396] （3 个 token）一个 token 可以是：
- 一个完整单词（常见英文词）
- 一个子词（"un"+"believable"）
- 一个字符（罕见词被拆成单字符）
- 一个特殊标记（
<eos>,<bos>等）
DeepSeek V4 Flash 有 129,280 个 token。
2. BPE（Byte Pair Encoding）算法
BPE 是最常用的分词算法，工作原理：
训练阶段（已完成，数据存在 GGUF 中）：
- 从字符级开始，每个字节是一个 token
- 统计相邻 token 对的出现频率
- 把最高频的 token 对合并为新 token
- 重复直到达到目标词表大小
- 记录合并顺序（rank，越小越优先）
编码阶段（ds4.c 中的 bpe_emit_piece）：
核心代码（行 13632-13698）：
c
for (;;) {
int best_i = -1;
int best_rank = INT32_MAX;
// 找到 rank 最小的相邻对
for (int i = 0; i + 1 < n_sym; i++) {
int rank = bpe_rank(vocab, &sym[i], &sym[i + 1]);
if (rank >= 0 && rank < best_rank) {
best_rank = rank;
best_i = i;
}
}
if (best_i < 0) break; // 没有可合并的对
// 合并 best_i 和 best_i+1
// ... 拼接字符串，移除 best_i+1 ...
n_sym--;
}3. GPT-2 字节级 BPE
标准 BPE 需要处理一个问题：输入文本包含所有可能的字节值（0-255），但其中有些不是合法的 Unicode 字符。
GPT-2 的解决方案：字节到 Unicode 码点的映射
c
static uint32_t gpt2_byte_to_codepoint(uint8_t b) {
// 可打印 ASCII 和部分 Latin-1 字符直接使用
if ((b >= 33 && b <= 126) || (b >= 161 && b <= 172) || (b >= 174)) {
return b;
}
// 不可打印字节映射到 256 开始的码点
// ...
}这样每个字节都能表示为一个合法的 Unicode 字符，BPE 可以在"字符级"上操作。
4. 预分词（Pre-tokenization）
在 BPE 合并之前，文本先按规则拆分成片段（行 13808-13876）：
"I love C99! 你好"
→ ["I", " love", " C", "99", "!", " 你", "好"]
↑ ↑ ↑ ↑ ↑
字母 空格+字母 数字 标点 CJK 字符预分词规则（JoyAI regex）：
- 数字最多 3 位一组
- CJK 字符单独处理
- 标点符号后跟字母
- 空格与后续字符组合
5. Chat 模板
LLM 不是直接处理原始文本，而是用特殊 token 标记对话结构：
<｜begin▁of▁sentence｜> ← BOS（句首）
System message here
<｜User｜> ← 用户消息开始
What is Redis?
<｜Assistant｜>💭 ← 助手回复开始 + 思考模式
Let me think about this...
📤 ← 思考结束
Redis is...
<｜end▁of▁sentence｜> ← EOS（句尾）ds4.c 的 encode_chat_prompt 函数（行 13940-13961）负责组装这些 token。
2. 采样策略
模型输出 129280 个原始分数（logits），但用户只需要一个词。采样策略决定怎么从 12 万个候选项中挑出一个——太确定则输出呆板，太随机则输出胡言。今天学习 softmax、temperature、top-k/p 在确定性和多样性之间找平衡。
设计决策推导：从 logits 到 token
问题 1：模型输出 129280 个 logits（原始分数），怎么变成概率？
└─ 方案：softmax — exp(x) / Σexp(x)，把任意实数映射到 [0,1] 且总和为 1
└─ 副作用：exp(大数) 会溢出 → 减去最大值后再 exp（数值稳定技巧）
问题 2：直接按概率随机采样（轮盘赌），输出太随机了怎么办？
└─ 方案 A：Temperature — logits / T 后再 softmax
T→0: 趋近 argmax（完全确定），T→∞: 趋近均匀分布（完全随机）
问题 3：即使调了温度，低概率的 token 仍可能被选中，输出不稳定？
└─ 方案 B：Top-K — 只保留概率最高的 K 个 token，其余归零
└─ 问题：K 是固定的，模型确定时 K 个太多，不确定时 K 个太少
问题 4：能不能让截断阈值自适应？
└─ 方案 C：Top-P（核采样）— 按概率降序排列，累加到 P 后截断
模型确定时：前几个 token 就凑够 P → 保留少 → 更确定
模型不确定时：需要很多 token 才凑够 P → 保留多 → 更多样
问题 5：Top-P 可能保留一些"和最高概率差距太大"的 token？
└─ 方案 D：Min-P — 只保留概率 >= 最高概率 × min_p 的 token
例：最高 0.5, min_p=0.1 → 保留所有 >= 0.05 的 → 砍掉尾部噪音
最终组合：Temperature 缩放 → Top-P + Min-P 双重过滤 → 轮盘赌采样C 知识点
1. 浮点运算技巧
数值稳定的 softmax：
c
// 先找最大值
float max_logit = DS4_NEG_INF;
for (uint32_t i = 0; i < n_vocab; i++)
if (logits[i] > max_logit) max_logit = logits[i];
// 减去最大值再取指数（防止溢出）
const float p = expf((v - max_logit) / temperature);为什么减去最大值？exp(大数) 会溢出变成 +inf，exp(大数 - 最大数) 的最大值是 exp(0) = 1，安全。
float 精度注意事项：
- ds4.c 用
double累加（double ss = 0.0），最后转回float，减少累加误差 isfinite(v)检查排除 NaN 和无穷大DS4_NEG_INF = -1e30f（不是-INFINITY），避免 NaN 传播
2. 插入排序 vs qsort
ds4.c 在 top-k 选择中用了两种排序：
插入排序（维护 top-k 数组）：
c
// 边扫描边维护已排序的 top-k，最多 1024 个元素
int j = n < top_k ? n++ : n - 1;
while (j > 0 && vals[j - 1] < v) {
vals[j] = vals[j - 1]; // 后移
ids[j] = ids[j - 1];
j--;
}
vals[j] = v;
ids[j] = (int)i;为什么用插入排序？
- 每次 only 移动最多 k 个元素
- 对于 k=1024，比 qsort 全排序快得多
- 时间复杂度：O(n × k)，当 k << n 时比 O(n log n) 好
qsort（全词表排序）：
c
// 当 top_k <= 0 时，对整个词表排序
qsort(cand, n, sizeof(cand[0]), sample_candidate_cmp_desc);标准库的快速排序，O(n log n)。
3. PRNG — xorshift64
c
static uint64_t sample_rng_next(uint64_t *state) {
uint64_t x = *state;
if (x == 0) x = 0x9e3779b97f4a7c15ULL; // 黄金比例常数
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*state = x;
return x * 0x2545f4914f6cdd1dULL;
}
static float sample_rng_f32(uint64_t *state) {
const uint64_t x = sample_rng_next(state);
return (float)((x >> 40) & 0xffffffu) / 16777216.0f; // [0, 1)
}- xorshift64：3 次移位异或 + 一次乘法，非常快
- 零状态保护：如果 state 为 0，替换为黄金比例常数
- 浮点转换：取高 24 位，除以 2^24，得到 [0, 1) 均匀分布
4. union 类型转换（比较函数）
c
static int sample_candidate_cmp_desc(const void *a, const void *b) {
const sample_candidate *ca = a;
const sample_candidate *cb = b;
return (cb->logit > ca->logit) - (cb->logit < ca->logit);
}这是无分支的三路比较：
a > b返回 -1a == b返回 0a < b返回 1 比if/else更简洁，编译器可以生成无分支代码。
LLM 知识点
1. 采样算法概览
推理的最后一步：从 129,280 个 token 的概率分布中选择下一个 token。
2. Temperature
c
const float p = expf((v - max_logit) / temperature);- temperature = 0：贪心解码（argmax），总是选概率最高的 token。输出确定、无聊
- temperature < 1：增强高概率 token 的优势，输出更集中
- temperature = 1：原始分布，不做缩放
- temperature > 1：拉平分布，输出更多样、更随机
DSML 结构性温度覆盖
生成工具调用时，服务器对 DSML 结构性 token 强制 temperature=0，只对参数载荷使用正常采样温度：
c
// 在 decode 循环中，每个 token 步骤检查 DSML 解码状态
if (dsml_decode_state_is_tool(state) &&
!dsml_decode_state_uses_payload_sampling(state)) {
// 标签、属性名、JSON 标点 → 强制 temperature=0
temperature = 0;
}
// string_body 和 json_string 状态 → 使用请求的正常温度这确保了工具调用语法始终可解析（确定性），同时文件内容、编辑文本等长载荷保持多样性（避免重复）。
贪心解码用于回归测试
temperature=0 的确定性使得它可以用于回归测试。ds4 的长上下文回归测试（test_long_story_fact_recall）用贪心解码验证模型的长程记忆能力：
- 用 Python 脚本生成虚构故事，在 190 个场景中嵌入 16 个人名-数字对应关系
- 加入干扰数字（年龄、价格等）测试模型的分辨能力
- 数字用英文拼写（"thirty-four"），模型需转换为数字（"34"）
- 采样参数：
temperature=0.0, top_k=0, top_p=1.0, frequency_penalty=0.0 - 输出格式固定为
Name=number，解析验证每个事实
相比之前的采样文本子串匹配（因随机性不稳定），贪心解码让测试完全确定性，只需 350 token 即可验证 16 个事实。
3. Top-K 采样
c
if (top_k > 0) {
// 维护概率最高的 top_k 个 token（插入排序）
for (uint32_t i = 0; i < n_vocab; i++) {
if (n == top_k && v <= vals[n-1]) continue; // 太低，跳过
// 插入到正确位置
}
}top_k = 50：只从概率最高的 50 个 token 中选- 防止选到极低概率的 token（"幻觉"）
- ds4.c 限制 top_k 最大 1024
4. Top-P（Nucleus）采样
c
float filtered_sum = 0.0f;
for (int i = 0; i < n; i++) {
filtered_sum += probs[i];
filtered++;
if (filtered_sum / sum >= top_p) break; // 累计概率够了
}top_p = 0.9：选最少的高概率 token，使累计概率 >= 90%- 比 top_k 更灵活：高确定性时选少量 token，不确定时选更多
- 两者可以组合：先 top-k，再 top-p
5. Min-P 采样
c
const float min_prob = (probs[0] / sum) * min_p;
for (int i = 0; i < n; i++) {
float p = probs[i] / sum;
if (i > 0 && p < min_prob) break; // 概率太低，排除
}min_p = 0.05：只保留概率 >= 最大概率 × 5% 的 token（ds4 现在默认启用，DS4_DEFAULT_MIN_P=0.05，同时top_p保持 1.0）- 相对阈值：不是固定值，而是相对于最高概率
- 适合高确定性场景（最高概率 99% 时只保留 > 4.95% 的）
- CLI、server、ds4-eval 均使用
DS4_DEFAULT_MIN_P作为默认值，thinking 模式的固定采样器也用min_p=0.05