TokTier: Exact Stateful Tokenization for Agentic LLM Serving
Zhenyu Zhang, Zhichao Cao
cs.CL, cs.DC, cs.PF
2026-08-01
coding agent 每轮只追加约 1.4K 字符却要重分词百万级上下文;TokTier 用增量修复加 GPU 全量分词处理这个浪费,在 vLLM 上把首 token 延迟降 16–34%,且与参考分词器零偏差。
coding agent(Claude Code、Codex 这类)每跑一步都要把整段会话历史重新发给模型。prefix cache 已经能让模型一侧复用 KV 状态,但前端那一步,也就是把请求文本切成 token,卡在缓存查询之前,所以每一轮都得从头扫一遍完整上下文。作者在两个真实 agent 生态里抓了 15.3 万次调用:中位数每次只追加约 1.4K 字符,只有 1.0–3.6% 的调用是真的冷启动或重建会话。命中率越高,这个被忽略的分词环节占比就越大。命中率到 94.1% 时,分词已经能占到首 token 延迟(TTFT)的 64%。
难点是分词不能简单复用上一轮的结果。分词不是可拼接的:tok(A) 接上 tok(B) 不等于 tok(AB)。会话末尾接一小段新文本,可能把边界往前推。比如上一轮结尾是「pipe」,这轮追加「line」,参考分词器会把「 pipeline」合成一个 token,末尾的 token 变了,后面所有位置顺移。因为 token 序列同时是 prefix cache 的键,这种漂移会悄悄废掉整个会话后续的缓存复用。固定一个重叠半径去重切并不安全:数字分组、空白前瞻、换行吸收能让这种影响越过任何选定的半径。
TokTier 只认一条契约:发出去的 token 序列永远等于参考分词器对完整文本的输出。两条执行路径对应两种调用模式。
绝大多数调用是会话续接,走增量修复。它保留会话上一轮的 token 序列,只对追加处附近一个窗口(默认 512 字符)重新分词,然后做一次稳定边界检查:在拼接处找一个字符类别切换点,且能证明这个点右边的预分词结果不依赖左边的文本。只有检查通过才拼接,失败就把窗口翻倍重试,最多五次,再不行就退回完整参考分词。一次续接的工作量是 O(新文本加窗口),与上下文长度无关。第一档 512 字符窗口在 5.6 万次真实拼接里接受了 99.995%。
少数冷启动和重建调用没有可复用前缀,走 GPU 全量分词。GPT 系分词器先用一个正则做预分词,这个正则按定义是串行的,每次匹配从上一次结束处开始,没法直接并行。作者的观察是,他们研究的那些生产级分词模式其实从不依赖回溯。于是把正则拆成按字符类别的规则:字母、数字、空白、其他四类聚成最大同片段,一个字符是不是片段起点只取决于它在片段内的偏移、跨边界的有限回看和几个片段级汇总量。分类和汇总都靠并行扫描完成,片段起点判定变成每个字符独立的谓词。切好的片段再喂给按长度分档的 GPU BPE 流水线,短片段一个线程、中片段一个 warp、长片段一个 block。
一个采样约 5% 的影子校验器对线上流量重新比对参考实现,专抓那些依赖历史、单跑新进程发现不了的 bug。
| 指标 | 结果 | 对照 |
| 正确性 | 17 个分词器族、1.5×10¹⁰ 次切分检查、12.4 TB 真实文本、9.3 万步 agent 回放,零偏差 | 参考实现 |
| 增量修复延迟(100K–3M 字符) | 0.5–1.1 ms | 比全量快 437× |
| 对比 GigaToken(预热缓存) | 1M 字符快 2.1×、2M 快 3.0× | 当前最强缓存基线 |
| GPU 全量(1M 字符) | 0.87 ms | 比 HF 快 491×、比最快 CPU 方法快 23.4× |
| vLLM 在环(中位 TTFT / P99) | 降 16–34% / 降 23% | recorded burst |
| 容量(50ms P99 目标) | 4 核修复加 1 GPU 撑 1,821 req/s | 16 核无状态前端只有 40 |
最后一行那个 45× 是不同硬件比的,作者明确说它是系统容量结果,不是等资源的效率结论。
对一个已经把缓存命中率做到 94% 以上的 agent 服务,分词是剩下还能动的那块延迟。TokTier 的好处是不破坏正确性,发出去的 token 和原来一字不差,现有的模型和 prefix cache 照用,整套东西能直接插到 vLLM 前面。代价是它要常驻会话状态、要占一块 GPU 做全量分词,是给中大型部署用的优化,不是个人改改 prompt 就能享受的红利。
作者把局限写得很细。GPU 路径的瓶颈是精确 BPE 合并的依赖链深度乘以访存往返,不是带宽也不是算力,所以消费级 RTX 5090 反而比服务器卡快 11–17%,因为靠的是主频。17 个分词器族里有 2 个在数学上就不满足谓词条件,其中一个归一化器会抹掉空白结构,永远只能走全量。零偏差是对当前这批冻结的工件成立的,不代表未来分词器版本也成立,每出一个新快照都得重跑准入校验,影子校验器也得一直挂着。大于 30K 字符的追加会把 P99 顶过 10ms,路由器目前不会把这种大追加改走全量路径(那能快 6–28×),作者把这归为待认证的优化。