Elea Notes.

TokTier: prompt 缓存命中 94% 之后, 分词成了 TTFT 的 64%

编码 agent 每轮都重提交长转录。追加文本会改掉旧 token 的切分, 让前缀缓存静默失效。TokTier 用可证明的稳定边界做增量分词, 承诺输出与全量分词逐位相同。

/系统与工程/5 分钟/推测性强

编码 agent 每收到一个工具结果就把整段对话重新提交一次。服务端早就学会了缓存 KV 状态，不必重算注意力；但大多数前端仍然把整段请求文本从头分词一遍。TokTier 这篇论文量化了这件事的代价，并给出一个在正确性上可证的修法。

先说结论

  • 在 153,951 次真实调用（十个月的 Claude Code 与 Codex CLI 日常使用，六名用户九台机器）里，中位数一次调用只追加约 1.4K 字符，而中位上下文是 86K（Codex）到 123K（Claude Code）个 token。绝大多数调用是往一个大上下文里加一点点东西。
  • 车队级 prompt 缓存命中率为 94.1%。命中率越高，分词占首 token 延迟（TTFT）的比例越大：论文的组件测量里，命中率升到接近 0.99 时，分词从占 TTFT 的 10% 涨到 64%。缓存把该省的都省了，剩下没被优化的那一块就浮上来成了主项。
  • 不能简单地「只给新增部分分词然后拼接」。追加文本会改变旧文本尾部的 token 切分，而 token ID 序列正是前缀缓存的键，一旦漂移，整个会话后续的复用全部静默失效。
  • TokTier 的做法是：只在追加点附近的一个窗口内重新分词，并且只有在找到一个可证明的稳定边界之后才拼接，否则加宽窗口、最终退回全量分词。契约是「输出的 token ID 必须与全量参考分词逐位相同」。
  • 实测：增量修复在 100K 到 3M 字符规模上耗时 0.5 到 1.1 ms；在 17 个分词器家族、1.5×10101.5\times10^{10} 次切分检查、12.4 TB 真实文本语料上做差分测试，零分歧。接到 vLLM 上，TTFT 中位数下降 16% 到 34%。

机制

为什么追加会改掉旧 token

现代 BPE 分词分两步：先用一段正则把文本切成小片（pre-tokenization），再对每一片独立跑 BPE 合并。关键后果是，任意选定的文本位置并不是 token 边界。

论文给的真实例子（Llama-3.1-8B 分词器）：上一次请求的文本末尾是 pipe，这一次追加 line。下面用 _ 代表那个前导空格。

上次请求文本:  ... _pipe
本次追加:              line

独立分词（错）:   [_pipe] [line]      <- 两个 token
全量分词（对）:   [_pipeline]         <- 一个 token

参考分词器看到的是完整的 _pipeline，发一个 token。而把两边分开各自分词会发出两个。追加的文本改掉了旧前缀的最后一个 token，并让之后每个位置整体平移。

有两个机制在造成这个效果：pre-tokenizer 会因为右边来了新文本而移动片边界；片内的 BPE 合并顺序随之改变。

一个直觉上很自然的修法是「在追加点前后留一个固定的重叠半径，那段重算就安全了」。论文明确说这不是一条正确性规则：数字分组、空白 lookahead、换行吸收都能把影响推过任何选定的半径，他们的对抗性 oracle 对每一条他们能写出来的固定半径规则都造出了级联反例。

所以窗口在 TokTier 里只用来搜索一个可复用的边界，是否接受则取决于另一个从分词器家族推导出来的、逐请求的检查。

增量修复

存量:  [已缓存的 token 记录 ................ ]
                        |  取一段后缀 + 追加文本，重新分词
                        v
新算:                  [ 新鲜 token 记录 ... ]
                        |  比对新鲜与缓存的相等 run
                        v
                   (*) 相等 run 里是否含稳定 pre-tokenization 边界？
                    |- 是  -> 在该 run 末尾拼接，复用其左侧全部缓存
                    |- 否  -> 加宽窗口；仍失败则全量参考分词

带星号那一步（论文形式化里叫 certificate）是整个设计承重的地方：它检查的是 pre-tokenizer 可证明看不过去的那类位置。失败时的分支全部指向「做更多工作」，也就是更宽的窗口、全量重算、CPU 回退，而从不指向不同的 token ID。这个「失败方向单一」的性质是它敢对外承诺逐位相同的原因。

没有可复用前缀的调用

会话初始化和重建占 1.0% 到 3.6% 的调用，但它们带着完整上下文，可达上百万字符量级，是尾延迟的主要来源。这类调用没有前缀可拼，只能全量分词。

GPT 家族的 pre-tokenization 正则在通常写法下是串行的：每个匹配都从上一个匹配结束处开始。TokTier 把这段正则重写成等价的 run-local 规则，按字符类划分 run、规则只依赖 run 局部信息，从而去掉串行扫描，让精确 pre-tokenization 和 BPE 都能在 GPU 上跑。100 万字符的请求全量编码 0.87 ms。

为什么这样设计

这篇论文真正的贡献不是快，是把「快」和「精确」的关系倒过来。

已有工作的通行姿态是把分词复用当作近似优化：给个重叠半径，测一测没出错就上线。论文点了两个名字：LoPT 是唯一一篇经过同行评审的分段分词工作，它出厂的一个配置逃出了自己安全性定理的前提；Gigatoken 是被广泛采用的工业引擎，断言边界行为安全但没有证明。

代价是可见的。契约越硬，能走快路径的情况就越少，检查失败要加宽窗口甚至全量重算。TokTier 接受这个代价，换来的是可以放在服务里而不需要一个「万一分词错了怎么办」的应急预案。它还额外跑一个抽样的影子校验器（shadow verifier）在线复查真实流量，等于承认「证明过」和「实现对」是两件事。

数字上这笔交易是划算的：增量修复相对 HuggingFace 分词最高快 437 倍，在 1M 规模上比最强的缓存基线（Gigatoken，且已完全预热）快 2.1 倍。在 50 ms 的 P99 目标下，四个修复核加一块 GPU 支撑 1,821 请求每秒，而一个 16 核无状态前端在 40 请求每秒就饱和了。

边界

  • 论文的主数据集来自六名用户、九台机器的十个月使用，加上另一机构收集的 Claude Code 与 Codex 会话和一个公开的自主 agent 轨迹。论文自己说把趋势当动机、而不是当车队规模的预测。这不是行业普查。
  • 「分词占 TTFT 的 64%」是组件测量下、缓存命中率接近 0.99 时的数字，不是常态。命中率低的部署里这一项无关紧要，它恰恰是被缓存做得很好之后才暴露的问题。
  • 零分歧是在 17 个分词器家族上测出来的，不等于对任意未来分词器成立。稳定边界检查是逐家族推导的，新分词器需要重新做这份工作。
  • 这是 v1 预印本（2026 年 7 月 31 日提交），尚未经过同行评审。论文点名的两个前作各自出过安全性问题，按它自己的说法，这类工作的复杂度「经常被低估」。

来源

  1. TokTier: Exact Stateful Tokenization for Agentic LLM ServingarXiv 2607.29678v1