TokTier: Exact Stateful Tokenization for Agentic LLM Serving
2026-07-31 • Computation and Language
Computation and LanguageDistributed, Parallel, and Cluster ComputingPerformance
AI summaryⓘ
The authors address inefficiencies in large language model (LLM) serving systems, where repeated tokenization of long request texts slows down response times. They introduce TokTier, a system that saves time by only re-tokenizing small parts of a conversation when new text is added, and performs full tokenization on GPU when needed. This approach drastically speeds up processing compared to existing methods while ensuring accuracy, verified on a massive dataset without errors. The authors show TokTier improves real-time performance and supports a high number of requests per second with fewer computing resources.
large language modelstokenizationprompt cachingkey-value stateBPE (byte pair encoding)GPU accelerationsession continuationvLLMregex pre-tokenizationresponse latency
Authors
Zhenyu Zhang, Zhichao Cao
Abstract
LLM serving systems cache prompt KV state, yet most front ends still re-tokenize the full request text on every call. The cost lands on coding agents, which resubmit a long transcript after each small tool result, and reuse is hard because even a short append can change token boundaries near the end of the previous sequence. Across 153,951 calls from two agent ecosystems, the median call appends about 1.4K characters, and only 1.0-3.6% of calls start or rebuild a session with contexts of millions of characters. At a 94.1% fleet prompt-cache hit rate, tokenization reaches up to 64% of time to first token. TokTier is a stateful tokenization service with one contract: emitted token IDs are always identical to full reference tokenization of the request text. For a session continuation, it re-tokenizes a small window around the append and splices only after a per-request stable-boundary check, widening the window or falling back to full tokenization on failure. For a call without a reusable prefix, it decomposes GPT-family regex pre-tokenization into run-local rules and runs exact pre-tokenization and BPE on a GPU. A sampled shadow verifier re-checks live traffic. Across 17 tokenizer families, differential campaigns cover 1.5x10^10 split checks, a 12.4 TB real-text corpus, and 93,000+ replayed agent steps, with zero divergence. Incremental repair takes 0.5-1.1 ms from 100K to 3M characters, up to 437x faster than HF tokenization and 2.1x faster at 1M than the strongest cache-based baseline (Gigatoken) fully prewarmed. GPU full tokenization encodes a 1M-character request in 0.87 ms, up to 491x below HF and 23.4x below the fastest published CPU method. With vLLM, median time to first token drops 16-34% and P99 drops 23% under recorded bursts. Under a 50 ms P99 objective, four repair cores plus one GPU sustain 1,821 requests/s where a 16-core stateless front end saturates at 40.