TokTier: tokenization eats up to 64% of time-to-first-token in agent workloads, and stateful re-tokenization is 437x faster

arXiv·high signalXBlueskyLinkedInCopy link

A July 31 arXiv paper by Zhenyu Zhang and Zhichao Cao profiled 153,951 real calls from two agent ecosystems and found that even with prompt KV caching, frontend re-tokenization of the full transcript consumes up to 64% of time-to-first-token at high cache hit rates — a cost nobody instruments. TokTier does incremental repair (re-tokenizing only a window around appended text) plus GPU pre-tokenization, guaranteeing bit-identical token IDs versus full reference tokenization: 437x faster than HF tokenizers, 1M-character requests encoded in 0.87 ms, and 1,821 req/s versus 40 for stateless. Wired into vLLM it cut median TTFT 16-34% and P99 23%. If you run long-transcript agent loops, this is a latency line item you are almost certainly paying and not measuring.