TokTier: Exact Stateful Tokenization for Agentic LLM Serving

TL;DR - TokTier is a stateful tokenization service for agentic LLM serving that incrementally re-tokenizes only a window around appended text (with GPU-accelerated full tokenization as fallback), while guaranteeing token IDs identical to full reference tokenization. It matters because, once prompt KV caching is highly effective (94.1% hit rate), tokenization itself becomes up to 64% of time to first token.

• Trace analysis of 153,951 calls from two agent ecosystems: median call appends ~1.4K characters, and only 1.0–3.6% of calls start or rebuild a session, motivating incremental reuse.
• Exactness contract: a per-request stable-boundary check gates splicing, widening the window or falling back to full tokenization; a sampled shadow verifier re-checks live traffic.
• GPU path decomposes GPT-family regex pre-tokenization into run-local rules, encoding a 1M-character request in 0.87 ms (up to 491x below HF, 23.4x below the fastest published CPU method); incremental repair is 0.5–1.1 ms for 100K–3M chars (up to 437x faster than HF, 2.1x faster than a fully prewarmed Gigatoken at 1M).
• Validation showed zero divergence across 17 tokenizer families, 1.5x10^10 split checks, a 12.4 TB corpus, and 93,000+ replayed agent steps; with vLLM, median TTFT drops 16–34% and P99 drops 23%, sustaining 1,821 req/s (four repair cores + one GPU) under a 50 ms P99 target vs. 40 for a 16-core stateless front end.