arXiv paper: TokTier: Exact Stateful Tokenization for Agentic LLM Serving

An arXiv paper introduces TokTier, a stateful tokenizer designed to eliminate a major bottleneck in serving LLM-based coding agents. These agents frequently resubmit long conversation transcripts after each tool action, causing tokenization costs to account for up to 64% of time-to-first-token even when prompt caches achieve a 94.1% hit rate. TokTier guarantees exact token IDs matching full re-tokenization of the request text, using incremental repair on session continuations (only re-tokenizing a small window) and GPU-parallel full tokenization for new requests, with a shadow verifier ensuring correctness in production. Empirically, across 17 tokenizer families and over 93,000 replayed agent steps, TokTier exhibited zero token-level divergence from reference tokenization. Its incremental repair processes 100K to 3M characters in 0.5--1.1 ms (up to 437× faster than HuggingFace), while its GPU full tokenization encodes 1M characters in 0.87 ms (up to 491× below HuggingFace). When integrated with the vLLM serving framework, median time-to-first-token dropped 16–34% and P99 dropped 23% under measured workloads. Under a 50 ms P99 latency budget, a configuration of four repair CPU cores