ArXiv

TokTier: Exact Stateful Tokenization for Agentic LLM Serving

2026-07-31 · 17:56 UTC ·Zhenyu Zhang, Zhichao Cao ·1 min read
Authors
Zhenyu Zhang, Zhichao Cao
Categories
cs.CL, cs.DC, cs.PF
arXiv
https://arxiv.org/abs/2607.29678v1
PDF
https://arxiv.org/pdf/2607.29678v1

Brief

TokTier, a stateful tokenization service, removes costly full re-tokenization for agentic LLM serving while ensuring emitted token IDs match full-reference tokenization. Motivated by 153,951 calls with median 1.4K‑char appends and a 94.1% prompt-cache hit rate, it incrementally re-tokenizes around appends, runs GPU pre-tokenization/BPE for cold calls, and shadow-verifies traffic. Results show sub-ms repairs (0.5–1.1 ms), 0.87 ms GPU encoding for 1M chars, large speedups vs. HF, and substantial TTF and throughput gains (e.g., 1,821 req/s under 50 ms P99).

Why it matters

TokTier is a stateful tokenization service that guarantees emitted token IDs exactly match full-reference tokenization while incrementally re-tokenizing only a small window around appends with a stable-boundary check; fallback to full GPU pre-tokenization/BPE is used when needed.

Key details

  • On real agent workloads (153,951 calls, median append ≈1.4K characters, 94.1% fleet prompt-cache hit rate) TokTier does incremental repair in 0.5–1.1 ms for 100K–3M characters (up to 437× faster than HuggingFace), GPU full tokenization encodes 1M characters in 0.87 ms (up to 491× faster than HF), and integration with vLLM cut median time-to-first-token 16–34% and P99 23%.
  • Large validation: differential campaigns covered 1.5×10^10 split checks, a 12.4 TB real-text corpus and 93k+ replayed agent steps with zero divergence; under a 50 ms P99 target, four repair cores plus one GPU sustain 1,821 req/s versus a 16-core stateless front end that saturates at 40 req/s.
Source evidence

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.

Comment: 24 pages, 18 figures, 8 tables